题目描述
给你二叉搜索树的根节点 root
,同时给定最小边界 low
和最大边界 high
。通过修剪二叉搜索树,使得所有节点的值在 [low, high]
中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
示例 1:
1 2
| 输入:root = [1,0,2], low = 1, high = 2 输出:[1,null,2]
|
示例 2:
1 2
| 输入: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
来源:力扣(LeetCode)
题解
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势。
迭代
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| public TreeNode trimBST(TreeNode root, int low, int high) { TreeNode current = root; TreeNode prev = null; while (current != null) { while (current != null && current.val >= low) { prev = current; current = current.left; } if (current == null) break; current = current.right; if (prev != null) prev.left = current; else root = current; } current = root; prev = null; while (current != null) { while (current != null && current.val <= high) { prev = current; current = current.right; } if (current == null) break; current = current.left; if (prev != null) prev.right = current; else root = current; } return root; }
|
迭代
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| public TreeNode trimBST(TreeNode root, int low, int high) { while (root != null && (root.val < low || root.val > high)) { root = (root.val < low) ? root.right : root.left; } if (root == null) return null; for (TreeNode node = root; node.left != null; ) { if (node.left.val < low) node.left = node.left.right; else node = node.left; } for (TreeNode node = root; node.right != null; ) { if (node.right.val > high) node.right = node.right.left; else node = node.right; } return root; }
|
递归
1 2 3 4 5 6 7 8 9
| 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); root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; }
|
参考资料
__END__