Contents

[Golang][Leetcode][BinaryTree]刷題系列-501-Find Mode in Binary Search Tree


501. Find Mode in Binary Search Tree


Level : Easy

原題連結 : Click

題目 :

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example :

Note

Example 1:

Input: root = [1,null,2,2] Output: [2]

Example 2:

Input: root = [0] Output: [0]


解題思路 :

  • 這題的概念可以參考 leetcode530題解

  • 題目需要我們找出所有的"Modes",題目跟我們定義Modes指的是該BST中出現次數最頻繁的那些node

  • 題目是建立在BST定義是沒有限制every node is unique,所以可以有相同值

  • 這題可以分成兩個層面來想 1.一般binary tree 2.Binary search tree

    1. 若是一般的binary tree找modes,可以直接隨便一個遍歷方式,並用map去計算次數
    2. 若是BST那肯定第一個會想到用inorder有序排列的特性去解決此題目

  • BST若用inorder遍歷就會形成一個由小到大的有序排列,利用這個特性這題會變得非常簡單
  • 相當於在一個由小到大排序的數組中找出出現頻率最高的數字們

Recursive解法-Inorder

  • time complexity: O(n) , space complexity: O(n)

Runtime: 8 ms, faster than 96.88% of Go online submissions for Find Mode in Binary Search Tree.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func findMode(root *TreeNode) []int {
    
    var resQueue []int
    
    var count int
    
    var max_count int
    
    var pre *TreeNode
    
    var traversal func(*TreeNode) 
    
    
    traversal = func(node *TreeNode) {
        
        if node == nil {
            return
        }
        
        traversal(node.Left)
        
        if pre != nil && node.Val == pre.Val {
            count++
        }else {
            pre = node
            count = 1
        }
        
        if count > max_count {
            max_count = count
            resQueue = append(resQueue, node.Val)

            if len(resQueue) > 1 {
                resQueue = resQueue[len(resQueue)-1:]
            }
        }else if count == max_count {
            resQueue = append(resQueue, node.Val)
        }
        
        traversal(node.Right)
    
    }
    
    traversal(root)
    
    return resQueue
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!