Leetcode 669 修剪二叉搜索树-拓冰建站

题意理解：

题目给出一个区间，对二叉树进行调整，值不在此区间的节点需要被剪掉，修建后的树，依然是一棵二叉树。

再次明确，二叉树中间节点大于所有左子树，小于所有右子树，中序遍历是严格单调增的序列。

难点：

节点删减会导致树的结构发生变化。叶子节点的删减是简单的，麻烦的是中间节点删除后，需要对其子树进行操作，操作不总是唯一的。

每个节点的判断思路：

若此节点需要被剪掉，则有：

该节点的值大于high值，根据二叉搜索树的性质，其右子树所有值大于该节点值，右子树整个剪掉，当前节点由左子树继承，继续判断左子树上是否有需要删减的节点。

该节点的值小于low值，根据二叉搜索树的性质，其左子树所有值小于该节点的值，左子树整个剪掉，当前节点由右子树继承，继续判断右子树是否由需要删减的节点。

解题方法：

递归迭代

1.递归

解决递归树类问题，可以按照一下三步走：什么遍历？输入是什么输出是什么？终止条件是什么？

这里总是先对中间节点进行判断，所以应该是先序遍历，输入是树和low high,终止条件是碰到null

//669. 修剪二叉搜索树public TreeNode trimBST(TreeNode root, int low, int high) {//先序遍历//  中间节点处理if(root==null) return null;if(root.val<low){//小于最小值，区间外，剪（当前+左子树)return  trimBST(root.right,low,high);} else if (root.val>high) {//大于最大值，区间外，剪（当前+右子树)return trimBST(root.left,low,high);}//  左子树处理if(root.left!=null) root.left=trimBST(root.left,low,high);//  右子树处理if(root.right!=null) root.right=trimBST(root.right,low,high);return root;}

2.迭代

迭代的话，这里有个非常特殊的地方，当我们使用区间来修剪树的时候，我们总是从树的最左侧剪掉小于low的值节点，从最右侧剪掉高于high的点。

所以在递归时，我们的思路是：先找到一个合适的root的节点，然后从左外侧往里修剪小于low的值，从有外侧往里剪大于high的值，最终我们得到一个符合条件的root.

public TreeNode trimBST(TreeNode root, int low, int high) {if(root==null) return null;//有一个符合要求的头节点while(root!=null&&(root.val<low||root.val>high)){if(root.val<low) root=root.right;if(root.val>high) root=root.left;}TreeNode cur=root;//处理左孩子小于lowwhile(cur!=null){//处理if(cur.left!=null&&cur.left.val<low){cur.left=cur.left.right;}else{cur=cur.left;}}cur=root;//处理最小值大于highwhile(cur!=null){if(cur.right!=null&&cur.right.val>high){cur.right=cur.right.left;}else{cur=cur.right;}}return root;}