day14

来源：恒创科技编辑：恒创科技编辑部

2022-09-09 14:02:46

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

力扣题目链接

题目

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root =[6,2,8,0,4,7,9,null,null,3,5]

day14_算法

示例 1：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2,

说明：

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

递归解法

思路

确定递归函数返回值以及参数：参数就是当前节点，以及两个结点 p、q，返回值是要返回最近公共祖先

public TreeNode traversal(TreeNode root, TreeNode p, TreeNode q)

确定终止条件：遇到空返回就可以了

if (root == null) {
            return null;
        }

确定单层递归的逻辑：如果root.val 大于p.val，同时root.val 大于q.val，那么就应该向左遍历（说明目标区间在左子树上）如果root.val 小于p.val，同时root.val 小于q.val，那么就应该向右遍历（说明目标区间在右子树上）需要注意的是此时不知道p和q谁大，所以两个都要判断

if (root.val > p.val && root.val > q.val) {
            TreeNode left = traversal(root.left, p, q);
            if (left != null) {
                return left;
            }
        }

        if (root.val < p.val && root.val < q.val) {
            TreeNode right = traversal(root.right, p, q);
            if (right != null) {
                return right;
            }
        }

剩下的情况，就是cur节点在区间（p.val <= cur.val && cur.val <= q.val）或者（q.val <= cur.val && cur.val <= p.val）中，那么cur就是最近公共祖先了，直接返回 cur

return root;

代码实现

/**
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 *
 * @author xiexu
 * @create 2022-03-14 3:51 PM
 */
public class _235_二叉搜索树的最近公共祖先_二叉搜索树优化 {

    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) {
            return null;
        }
        if (root.val > p.val && root.val > q.val) {
            TreeNode left = traversal(root.left, p, q);
            if (left != null) {
                return left;
            }
        }

        if (root.val < p.val && root.val < q.val) {
            TreeNode right = traversal(root.right, p, q);
            if (right != null) {
                return right;
            }
        }

        return root;
    }

}

迭代解法

代码实现

/**
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 *
 * @author xiexu
 * @create 2022-03-14 3:51 PM
 */
public class _235_二叉搜索树的最近公共祖先_迭代 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            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 {
                return root;
            }
        }
        return root;
    }

}

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

力扣题目链接

题目

给定二叉搜索树（BST）的根节点root和要插入树中的值value，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

示例 1：

day14_广度优先遍历_02

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]

day14_广度优先遍历_03

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

树中的节点数将在 [0, 10^4]的范围内。
-10^8 <= Node.val <= 10^8
所有值 Node.val 是 独一无二 的。
-10^8 <= val <= 10^8

递归解法

思路

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了

day14_二叉搜索树_04

例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，需要调整二叉树的结构么？并不需要。

确定递归函数参数以及返回值：参数就是根节点指针，以及要插入元素，返回类型为节点类型TreeNode

public TreeNode insertIntoBST(TreeNode root, int val)

确定终止条件：终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回

if (root == null) {
            TreeNode node = new TreeNode(val);
            return node;
        }

这里把添加的节点返回给上一层，就完成了父子节点的赋值操作了

确定单层递归的逻辑：搜索树是有方向了，可以根据插入元素的数值，决定递归方向

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

代码实现

/**
 * https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
 *
 * @author xiexu
 * @create 2022-03-14 4:30 PM
 */
public class _701_二叉搜索树中的插入操作 {

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            TreeNode node = new TreeNode(val);
            return node;
        }
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }

}

迭代解法

思路

在迭代法遍历的过程中，需要记录一下当前遍历的节点的父节点，这样才能做插入节点的操作

代码实现

/**
 * https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
 *
 * @author xiexu
 * @create 2022-03-14 4:30 PM
 */
public class _701_二叉搜索树中的插入操作_迭代 {

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode newRoot = root;
        TreeNode pre = root;
        while (root != null) {
            pre = root;
            if (root.val > val) {
                root = root.left;
            } else if (root.val < val) {
                root = root.right;
            }
        }
        if (pre.val > val) {
            pre.left = new TreeNode(val);
        } else {
            pre.right = new TreeNode(val);
        }
        return newRoot;
    }

}

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

力扣题目链接

题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；如果找到了，删除它。

示例 1:

day14_二叉搜索树_05

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

day14_算法_06

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0

示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 10^4].
-10^5 <= Node.val <= 10^5
节点值唯一
root 是合法的二叉搜索树
-10^5 <= key <= 10^5

思路

确定递归函数参数以及返回值：

public TreeNode deleteNode(TreeNode root, int key)

确定终止条件：遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了

if (root == null) {
            return null;
        }

确定单层递归的逻辑：有以下五种情况：第一种情况：没找到删除的节点，遍历到空节点直接返回了找到删除的节点：第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点动画中二叉搜索树中，删除元素7，那么删除节点（元素7）的左孩子就是5，删除节点（元素7）的右子树的最左面节点是元素8。将删除节点（元素7）的左孩子放到删除节点（元素7）的右子树的最左面节点（元素8）的左孩子上，就是把5为根节点的子树移到了8的左孩子的位置。要删除的节点（元素7）的右孩子（元素9）为新的根节点。

代码实现

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

669. 修剪二叉搜索树

力扣题目链接

题目

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

day14_leetcode_07

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

day14_二叉搜索树_08

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

树中节点数在范围 [1, 10^4] 内
0 <= Node.val <= 10^4
树中每个节点的值都是 唯一 的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 10^4

思路

详细题解见：

代码随想录

代码实现

/**
 * https://leetcode-cn.com/problems/trim-a-binary-search-tree/
 *
 * @author xiexu
 * @create 2022-03-14 10:13 PM
 */
public class _669_修剪二叉搜索树 {

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        // 如果该节点的值小于最小值，则该节点更换为该节点的右节点值，继续遍历
        if (root.val < low) {
            TreeNode right = trimBST(root.right, low, high);
            return right;
        }
        // 如果该节点的值大于最大值，则该节点更换为该节点的左节点值，继续遍历
        if (root.val > high) {
            TreeNode left = trimBST(root.left, low, high);
            return left;
        }
        // root在[low,high]范围内
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

}

108. 将有序数组转换为二叉搜索树

力扣题目链接

题目

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

day14_深度优先遍历_09

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9]

day14_深度优先遍历_10

示例 2：

day14_广度优先遍历_11

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1]

代码实现

/**
 * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
 *
 * @author xiexu
 * @create 2022-03-15 9:43 AM
 */
public class _108_将有序数组转换为二叉搜索树 {

    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }

    // 左闭右闭区间[left, right]
    public TreeNode traversal(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root;
    }

}

538. 把二叉搜索树转换为累加树

力扣题目链接

题目

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node的新值等于原树中大于或等于node.val的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。

示例 1：

day14_深度优先遍历_12

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 10^4 之间。
每个节点的值介于 -10^4 和 10^4

递归解法

思路

从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。

代码实现

/**
 * https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
 *
 * @author xiexu
 * @create 2022-03-15 10:11 AM
 */
public class _538_把二叉搜索树转换为累加树 {

    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        return traversal(root);
    }

    // 按右中左顺序遍历，累加即可
    public TreeNode traversal(TreeNode root) {
        if (root == null) {
            return null;
        }
        traversal(root.right);
        sum += root.val;
        root.val = sum;
        traversal(root.left);
        return root;
    }

}

迭代解法

思路

迭代法其实就是中序模板题了

代码实现

/**
 * https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
 *
 * @author xiexu
 * @create 2022-03-15 10:11 AM
 */
public class _538_把二叉搜索树转换为累加树_迭代 {

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        traversal(root);
        return root;
    }

    public void traversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 记录累加值
        int sum = 0;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.right; // 右
            } else {
                cur = stack.pop(); // 中
                sum += cur.val;
                cur.val = sum;
                cur = cur.left; // 左
            }
        }
    }

}