530.二叉搜索树的最小绝对差

文章：24. 二叉搜索树的最小绝对差

题目：530. 二叉搜索树的最小绝对差

【思路】

递归

二叉搜索树中采用中序遍历，其实就是一个有序数组。

最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int min = Integer.MAX_VALUE;
    TreeNode pre;
    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        return min;
        
    }
    public void traversal(TreeNode node){
        if(node == null)return ;
        traversal(node.left);
        if(pre!=null){
            min = Math.min(min,node.val-pre.val);
        }
        pre = node;
        traversal(node.right);
        return ;

    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func getMinimumDifference(root *TreeNode) int {
    min:=math.MaxInt64
   var pre *TreeNode  //不可以将pre定义为&TreeNode{}  这样的话默认val为0了
    var traversal func(root *TreeNode) 
    traversal = func(root *TreeNode){
        if root == nil{
            return 
        }
        traversal(root.Left)
        if pre != nil && root.Val - pre.Val < min{
            min = root.Val - pre.Val
        }
        pre = root
        traversal(root.Right)
        return
    }
    traversal(root)
    return min
}

501.二叉搜索树中的众数

文章：25. 二叉搜索树中的众数

题目：501. 二叉搜索树中的众数

【思路】

如果不是二叉搜索树：

最直观的方法是把整个树都遍历一次，用map统计频率，把频率排序，最后取前面高频的元素的集合。

如果是二叉搜索树：

是搜索树的话，中序遍历就是有序的。

遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后把出现频率最高的元素输出即可。

  • Java
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
class Solution {
    ArrayList<Integer>resList;
    int maxCount ;
    int count;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        findMode1(root);
        int[] res = new int[resList.size()];
        for(int i =0 ;i<resList.size();i++){
            res[i] = resList.get(i);
        }
        return res;
    }
    public void findMode1(TreeNode root){
        if(root == null){
            return;
        }
        findMode1(root.left);
        int rootVal = root.val;
        if(pre == null || rootVal != pre.val){
            count = 1;
        }else{
            count++;
        }
        if(count > maxCount){
            resList.clear();
            resList.add(rootVal);
            maxCount = count;
        }else if(count== maxCount){
            resList.add(rootVal);
        }
        pre = root;
        findMode1(root.right);
    }
}
  • Go实现
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
func findMode(root *TreeNode) []int {
    res :=[]int{}
    count := 1    //初始次数统一是1
    maxCount :=0 
    var pre *TreeNode

    var most func(root *TreeNode )
    most = func(root *TreeNode){
        if root == nil{
            return 
        }
        most(root.Left)
        if pre != nil {
            if  pre.Val == root.Val{
                count++
                
            }else{
                count =1
            }  
        }
        //记录res的频率
        if maxCount <= count{
            if count > maxCount{
                res = []int{root.Val}
                maxCount = count
            }else{
                res = append(res,root.Val)
            }
        }

        pre = root
        most(root.Right)
        return 
    }
    most(root)
    return res
}

236.二叉树的最近公共祖先

文章：26. 二叉树的最近公共祖先

题目：236. 二叉树的最近公共祖先

【思路】

从下往上遍历，后序遍历

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return traversal(root,p,q);
    }   
    public TreeNode traversal(TreeNode root ,TreeNode p,TreeNode q){
        if(root == null || root.val == p.val ||root.val == q.val){
            return root;
        }
        TreeNode left = traversal(root.left,p,q);
        TreeNode right = traversal(root.right,p,q);
        if(left != null && right != null)return root;
        if(left == null && right != null)return right;
        else if(left!= null && right== null)return left;
        else return null;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root== nil || root.Val == p.Val || root.Val == q.Val{
        return root
    }
    left := lowestCommonAncestor(root.Left,p,q)
    right := lowestCommonAncestor(root.Right,p,q)
    if left == nil && right != nil{
        return right
    }
    if left != nil && right == nil{
        return left
    }else if left!= nil && right != nil{
        //root是公共祖先
        return root
    } else{
        return nil
    } 
}

【算法总结】

  • 二叉搜索树的最小绝对差：使用递归，将二叉树全部遍历放进数组，然后循环比较差值即可
  • 二叉搜索树中的众数：使用递归，循环遍历二叉树放入数组，然后循环遍历数组，比较相邻的值是否相等，如果不相等则更新count的值；然后进行count和maxCount的比较，相等的话则更新maxCount 的值并把值写入res，不相等的话则将res置空后添加count的值，继续遍历完数列重复以上操作。
  • 二叉树的最近公共祖先：从下往上遍历二叉树，使用后序遍历，通过从下往上遍历节点，来获得p和q，如果当前节点的左孩子和右孩子不为空的话则返回该节点为最近公共祖先。