669. 修剪二叉搜索树

题目描述

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

算法分析

对于二叉搜索树的一个结点，它的左子树的所有结点的值均小于该结点的值，它的右子树的结点的值均大于该结点的值。故每当遇到一个结点：

如果它的值大于右边界，则放弃根节点和右子树，用它的左子树代替该根节点如果它的值小于左边界，则放弃根节点和左子树，用它的右子树代替该根节点 非递归可以用层序遍历的方法，每当某个结点在边界外，就用它的左子树或右子树顶上。递归解法由于要用子树代替当前结点，递归函数要带有返回值。

代码

非递归

public class Solution { public TreeNode trimBST(TreeNode root, int L, int R) { TreeNode dummy = new TreeNode(L); dummy.left=root; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(dummy); while(!queue.isEmpty()) { TreeNode cur=queue.poll(); while(cur.left!=null && (cur.left.val<L || cur.left.val>R)) { if(cur.left.val<L) cur.left=cur.left.right; else cur.left=cur.left.left; } while(cur.right!=null && (cur.right.val<L || cur.right.val>R)) { if(cur.right.val<L) cur.right=cur.right.right; else cur.right=cur.right.left; } if(cur.left!=null) queue.offer(cur.left); if(cur.right!=null) queue.offer(cur.right); } return dummy.left; } }

递归

public TreeNode trimBST(TreeNode root, int L, int R) { if(root==null) return null; root.left = trimBST(root.left,L,R); root.right = trimBST(root.right,L,R); if(root.val<L) return root.right; if(root.val>R) return root.left; return root; }