leetcode - [669] Trim a Binary Search Tree

问题描述

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, R]的范围内。

举个例子：

解法1

Thanks

LeetCode 669. Trim a Binary Search Tree - 花花酱 刷题找工作 EP35

@san89kalp

来看下示意图：

对于当前节点来说，可以分为三种情况：

第一种，如果当前节点正好在[L, R]范围内，那么我们继续前序递归遍历其左右节点。

第二种，如果当前节点大于R，那么说明什么？

说明它的右子树就不用看了，肯定都是大于R的。

所以，我们就要去遍历它的左子树，看看有没有符合条件的节点。

第三种，和第二种正好相反，以此类推。

来看下实现：

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

}

Enjoy it !