算法第十九天|二叉树

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

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 二叉搜索树的特点是根节点的值大于左子树，同时小于右子树
        // 后序遍历
        // 如果当前节点的值大于等于pq其中某一个,同时小于等于pq中的某一个
        // 因为是后续遍历，是从下网上，那么说明就找到了这个节点

        if (root.val > p.val && root.val > q.val) { // 同时大于两个节点的值，说明这两个节点都在该节点的左子树上
            return lowestCommonAncestor(root.left, p, q); // 只遍历其左子树即可，答案一定在它的左子树上
        }

        if (root.val < p.val && root.val < q.val) { // 同时小于两个节点的值，说明这两个节点都在该节点的右子树上
            return lowestCommonAncestor(root.right, p, q);
        }

        // 除此之外的结果，就是当前值是结果
        return root;
    }

701. 二叉搜索树中的插入操作

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        // 二叉搜索树，根节点比左子树的都大，比右子树的都小
        // 所有值 Node.val 是 独一无二 的。
        TreeNode cur = root;
        insertIntoRoot(cur, val);
        return root;
    }

    private void insertIntoRoot(TreeNode cur, int val) {
        if (cur.val > val) {
            if (cur.left != null) {
                insertIntoRoot(cur.left, val);
            } else {
                cur.left = new TreeNode(val);
                return;
            }
        }

        if (cur.val < val) {
            if (cur.right != null) {
                insertIntoRoot(cur.right, val);
            } else {
                cur.right = new TreeNode(val);
                return;
            }
        }
    }

当前节点大于给定值，那么说明答案在左子树

当前节点小于给定值，那么说答案在右子树

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

 public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        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;
            }
        } else {
            if (root.val > key) {
                root.left = deleteNode(root.left, key);
            } else {
                root.right = deleteNode(root.right, key);
            }
        }
        return root;
    }

当左右子树都有值的时候，需要将当前的左子树放入右子树的最左边叶子节点的左节点