[LeetCode] 669. Trim a Binary Search Tree

mayaohua 發布于2019-08-16 13:38 / 2809人閱讀

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;
    }
}

云服務器 GPU云服務器 binary-search-tree binary-tree binary-search LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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