Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input: 1 / \ 0 2 L = 1 R = 2Output: 1 \ 2
Example 2:
Input: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3Output: 3 / 2 / 1
解法1:
凡是树的题目无非DFS，BFS，递归或者迭代做，仅此而已。
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def trimBST(self, root, L, R): """ :type root: TreeNode :type L: int :type R: int :rtype: TreeNode """ # use DFS, root first then left and right # if L <= root.val <= R: # new_root with root.val; # new_root.left = self.trimBST(root.left, L, root.val) # new_root.right = self.trimBST(root.right, root.val, R) # return new_root # elif root.val < L: # return self.trimBST(root.right, L, R) # elif root.val > R: # return self.trimBST(root.left, L, R) if root is None: return None if L <= root.val <= R: new_root = TreeNode(root.val) new_root.left = self.trimBST(root.left, L, root.val) new_root.right = self.trimBST(root.right, root.val, R) return new_root elif root.val < L: return self.trimBST(root.right, L, R) elif root.val > R: return self.trimBST(root.left, L, R)
迭代解法：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode trimBST(TreeNode root, int L, int R) { if (root == null) { return root; } while (root.val < L || root.val > R) { if (root.val < L) { root = root.right; } if (root.val > R) { root = root.left; } } TreeNode dummy = root; while (dummy != null) { while (dummy.left != null && dummy.left.val < L) { dummy.left = dummy.left.right; } dummy = dummy.left; } dummy = root; while (dummy != null) { while (dummy.right != null && dummy.right.val > R) { dummy.right = dummy.right.left; } dummy = dummy.right; } return root; }}