[LeetCode] 669. Trim a Binary Search Tree

mayaohua 发布于2019-08-16 13:38 / 2715人阅读

Problem

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 = 2

Output: 
    1
      
       2

Example 2:

Input: 
    3
   / 
  0   4
   
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1

Solution Recursive

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

Iterative

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        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;
    }
}

海外云主机私有云 binary-search-tree binary-tree binary-search LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72068.html

前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。题目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

codercao 2019-08-15 10:56 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。题目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

AlphaWatch 2019-08-15 10:56 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求判断一个树是否是二叉查找树。二叉查找树即满足当前节点左子树的值均小于当前节点的值，右子树的值均大于当前节点的值。思路一可以看到，对二叉查找树的中序遍历结果应当是一个递增的数组。这里我们用堆栈的方式实现中序遍历。题目要求 given a binary tree, determine if it is a valid binary search tree (BST). Assu...

songze 2019-08-15 10:56 评论0 收藏0
[Leetcode] Validate Binary Search Tree 验证二叉搜索树

摘要：注意这里的结构和不同的二叉树遍历一样，如果到空节点就返回，否则递归遍历左节点和右节点。唯一不同是加入了和，所以要在递归之前先判断是否符合和的条件。代码如果该节点大于上限返回假如果该节点小于下限返回假递归判断左子树和右子树 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...

fuchenxuan 2019-08-14 12:40 评论0 收藏0