二叉树31：修剪二叉搜索树

主要是我自己刷题的一些记录过程。如果有错可以指出哦大家一起进步。
转载代码随想录
原文链接
代码随想录
leetcode链接669. 修剪二叉搜索树

题目

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

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

示例

示例 1

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

示例 2

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

提示

思路

迭代法

如图

从图中可以看出需要重构二叉树想想是不是本题就有点复杂了。

其实不用重构那么复杂。

在上图中我们发现节点0并不符合区间要求那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了就是把节点0从二叉树中移除如图

理解了最关键部分了我们再递归三部曲

1. 确定递归函数的参数以及返回值

这里我们为什么需要返回值呢

因为是要遍历整棵树做修改其实不需要返回值也可以我们也可以完成修剪其实就是从二叉树中移除节点的操作。

但是有返回值更方便可以通过递归函数的返回值来移除节点。

这样的做法在二叉树搜索树中的插入操作和二叉树搜索树中的删除操作中大家已经了解过了。

代码如下

TreeNode* trimBST(TreeNode* root, int low, int high)

2. 确定终止条件

修剪的操作并不是在终止条件上进行的所以就是遇到空节点返回就可以了。

if (root == nullptr ) return nullptr;

3. 确定单层递归的逻辑

如果root当前节点的元素小于low的数值那么应该递归右子树并返回右子树符合条件的头结点。

代码如下

if (root->val < low) {
    TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
    return right;
}

如果root(当前节点)的元素大于high的那么应该递归左子树并返回左子树符合条件的头结点。

代码如下

if (root->val > high) {
    TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
    return left;
}

接下来要将下一层处理完左子树的结果赋给root->left处理完右子树的结果赋给root->right。

最后返回root节点代码如下

root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;

此时大家是不是还没发现这多余的节点究竟是如何从二叉树中移除的呢

在回顾一下上面的代码针对下图中二叉树的情况

如下代码相当于把节点0的右孩子节点2返回给上一层

if (root->val < low) {
    TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
    return right;
}

然后如下代码相当于用节点3的左孩子 把下一层返回的 节点0的右孩子节点2 接住。

root->left = trimBST(root->left, low, high);

此时节点3的左孩子就变成了节点2将节点0从二叉树中移除了。

最后整体代码如下

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr ) return nullptr;
        if (root->val < low) {
            TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
            return right;
        }
        if (root->val > high) {
            TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
            return left;
        }
        root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
        root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
        return root;
    }
};

精简之后代码如下

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        if (root->val < low) return trimBST(root->right, low, high);
        if (root->val > high) return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

只看代码其实不太好理解节点是如何移除的这一块大家可以自己再模拟模拟

迭代法

因为二叉搜索树的有序性不需要使用栈模拟递归的过程。

在剪枝的时候可以分为三步

将root移动到[L, R] 范围内注意是左闭右闭区间
剪枝左子树
剪枝右子树

代码如下

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;

        // 处理头结点让root移动到[L, R] 范围内注意是左闭右闭
        while (root != nullptr && (root->val < L || root->val > R)) {
            if (root->val < L) root = root->right; // 小于L往右走
            else root = root->left; // 大于R往左走
        }
        TreeNode *cur = root;
        // 此时root已经在[L, R] 范围内处理左孩子元素小于L的情况
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;

        // 此时root已经在[L, R] 范围内处理右孩子大于R的情况
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

总结

修剪二叉搜索树其实并不难但在递归法中大家可看出我费了很大的功夫来讲解如何删除节点的这个思路其实是比较绕的。

最终的代码倒是很简洁。

如果不对递归有深刻的理解这道题目还是有难度的

本题我依然给出递归法和迭代法初学者掌握递归就可以了如果想进一步学习就把迭代法也写一写。

自己的代码

class Solution {
public:
	TreeNode* trimBST(TreeNode* root, int low, int high) {
		if (!root)	return nullptr;		//确定终止条件
		if (root->val < low) {			//root->val值小于区间左端
			return trimBST(root->right, low, high);
		}
		else if (high < root->val) {	//root->val值大于区间右端
			return trimBST(root->left, low, high);
		}
		else {							//root->val值在区间内包含等于
			root->left = trimBST(root->left, low, high);
			root->right = trimBST(root->right, low, high);
		}
		return root;
	}
};