代码随想录第二十二天

Posted on In

235 二叉搜索树的最近公共祖先

复习 236 二叉树的最近公共祖先

利用后序遍历整个二叉树

记住回溯过程
左边有返回左边，右边有返回右边，两边都有返回中间，两边都没有就是null，最后回溯到最后搜到了就有值
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == q || root == p) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    if (left != null && right == null) return left;

    else if (left == null && right != null) return right;
    else return null;
}

}

此题利用二叉搜索树的特点，不需要自下而上遍历，因为公共祖先一定是在p和q之间的值，那么自上而下遍历二叉树，找到的第一个p和q的中间值的位置就是他们的最近公共祖先

自己利用dfs记录深度，返回root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    TreeNode result;
    int minDepth = Integer.MAX_VALUE;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, 0, p, q);
        return result;
    }

    private void dfs(TreeNode root, int depth, TreeNode p, TreeNode q){
        depth++;

        if ((root.val >= p.val && root.val <= q.val) || (root.val <= p.val && root.val >=q.val)){
            if (depth < minDepth){
                minDepth = depth;
                result = root;
            }
        } 

        if (root.left != null) dfs(root.left, depth, p, q);
        if (root.right != null) dfs(root.right, depth, p, q);
    }
}

简便写法，如果root值比两个值都大，就在root.left, 如果root值比两个值都小，就在root.right, 剩余的情况就是root

1
2
3
4
5
6
7
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        else if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        else return root;
    }
}

迭代

只需要在root值在p和q中间时即可返回root

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) {
        while (true){
            if (root.val > p.val && root.val > q.val){
                root = root.left;
            } else if (root.val < p.val && root.val < q.val){
                root = root.right;
            } else {
                break;
            }
        }

        return root;
    }
}

701 二叉搜索树中插入

如果不考虑重构二叉树，只需要找到空节点并且插入所需节点即可，遍历二叉搜索树时

遇到null值建立新TreeNode, 只比较root和val的值即可，root > val 构建左树，root < val 构建右树

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (root.val > val) root.left = insertIntoBST(root.left, val);
        if (root.val < val) root.right = insertIntoBST(root.right, val);

        return root;
    }
}

迭代法就是遍历父节点，找到位置

450 删除二叉搜索树中的节点

删除二叉搜索树节点中需要重构二叉树

有五种情况：

  1. 没找到删除的节点，遍历到空节点返回
  2. 左右孩子都为空，直接删除节点
  3. 删除节点左孩子为空，右孩子不为空，删除节点，右孩子补位
  4. 删除节点右孩子为空，左孩子不为空，删除节点，左孩子补位
  5. 左右孩子都不为空，将删除节点的左子树头节点放到删除节点的右子树最左面节点的左孩子上，返回删除节点右孩子为新根节点
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
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;

        if (root.val == key){
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                TreeNode cur = root.right;
                while (cur.left != null){
                    cur = cur.left;
                }

                cur.left = root.left;
                root = root.right;

                return root;
            }
        }

        if (root.val > key) root.left = deleteNode(root.left, key);
        if (root.val < key) root.right = deleteNode(root.right, key);

        return root;
    }
}