java算法第21天 | 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先

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

这道题的二叉树是二叉搜索树，因此最小绝对差一定在中序遍历的相邻节点之间产生。
**思路：**用pre节点记录当前节点cur的前一个结点，cur.val-pre.val就是差值。不断更新差值找到最小的差值。

class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {
    if (cur == NULL) return;
    traversal(cur->left);   // 左
    if (pre != NULL){       // 中
        result = min(result, cur->val - pre->val);
    }
    pre = cur; // 记录前一个
    traversal(cur->right);  // 右
}
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

501.二叉搜索树中的众数

思路： 使用一个全局的动态数组result来存储当前出现次数最多的数（注意，可能后面还有出现次数更多的数），当遇到出现次数更多的数时，更新result中的数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res=new ArrayList<>();
    int maxCount=0;//记录最大出现次数
    int count=0;//记录当前节点的值出现的次数
    TreeNode pre;//保存前一个节点
    public int[] findMode(TreeNode root) {
        getMode(root);
        int[] result=new int[res.size()];
        int index=0;
        for(int i:res){
            result[index++]=i;
        }
        return result;
    }
    public void getMode(TreeNode node){
        if(node==null) return;
        getMode(node.left);
        if(pre==null) count=1;
        else{
            if(node.val==pre.val){
                count++;
            }else{
                count=1;
            }
        }
        if(count==maxCount) res.add(node.val);
        else if(count>maxCount){
            res.clear();
            res.add(node.val);
            maxCount=count;
        }
        pre=node;
        getMode(node.right);
        return;
    }
}
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

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

思路：
情况一：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

情况二：节点本身p(q)，它拥有一个子孙节点q§

其实情况一 和 情况二 代码实现过程都是一样的，也可以说，实现情况一的逻辑，顺便包含了情况二。

因为遇到 q 或者 p 就返回，这样也包含了 q 或者 p 本身就是 公共祖先的情况。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return getLowestCommonAncestor(root,p,q);
    }

    public TreeNode getLowestCommonAncestor(TreeNode node, TreeNode p, TreeNode q){
        if(node==null) return null;
        if(node==p || node==q) return node;
        TreeNode left=getLowestCommonAncestor(node.left,p,q);
        TreeNode right=getLowestCommonAncestor(node.right,p,q);
        if(left!=null && right!=null) return node;
        else if(left!=null && right==null) return left;
        else if(left==null && right!=null) return right;
        else return null;
    }
}
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