Tech Base

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.

 

這題首先要先瞭解所謂的二元搜尋樹，

二元搜尋樹有以下特點

• 左子樹所有節點的鍵值小於根節點的鍵值
• 右子樹所有節點的鍵值大於根節點的鍵值
• 左右子樹也都是二元搜尋樹
• 節點不會有重複值

所以若目前節點的鍵值小於 L 值，則該節點的左子樹也都會小於 L 值

同理，若目前節點的鍵值大於 R 值，則該節點的右子樹也都會大於 R 值

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