leetcode - [669] Trim a Binary Search Tree

2020/06/17

问题描述

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 !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory