国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

99. Recover Binary Search Tree

superw / 1671人閱讀

摘要：題目解答想法很簡單，找到兩個(gè)順序不對的點(diǎn)，交換。但是如何知道這兩個(gè)點(diǎn)的順序是不對的呢因?yàn)槭亲笾杏遥晕覀兛梢杂玫姆椒０宕a如下

題目：
Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

解答：
想法很簡單，找到兩個(gè)順序不對的點(diǎn)，交換。但是如何知道這兩個(gè)點(diǎn)的順序是不對的呢？因?yàn)锽ST是左<中<右，所以我們可以用in-order traverse的方法：
In-order traverse模板：

public void inOrderTraverse{
    inOrderTraverse(root.left);
    //do something
    inOrderTraverse(root.right);
}

代碼如下：

public class Solution {
    private TreeNode first = null, second = null;
    private TreeNode prev = new TreeNode(Integer.MIN_VALUE);
    
    public void recoverTree(TreeNode root) {
        Traverse(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    
    public void Traverse(TreeNode root) {
        if (root == null) return;
        
        Traverse(root.left);
        
        if (first == null && prev.val > root.val) {
            first = prev;
        }
        if (first != null && prev.val > root.val) {
            second = root;
        }
        prev = root;
        
        Traverse(root.right);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/64884.html

相關(guān)文章

  • leetcode 315 Count of Smaller Numbers After Self 以

    摘要：題目意思就是要一個(gè)個(gè)的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。然后將兩個(gè)不正確的點(diǎn)記錄下來，最后回原來正確的值。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹。思想來自于的代碼實(shí)現(xiàn)。 跳過總結(jié)請點(diǎn)這里：https://segmentfault.com/a/11... BST最明顯的特點(diǎn)就是root.left.val < root.val < root.right.v...

    inapt 評(píng)論0 收藏0

  • Inorder Preorder Postorder

    摘要：題目鏈接參考這篇文章鏈接題目鏈接還是一樣的，用，或者保存和。題目鏈接題目鏈接按照的順序最后再一下。 Inorder Binary Tree Inorder Traversal lc題目鏈接：https://leetcode.com/problems... recursion： public class Solution { public List inorderTraversa...

    caikeal 評(píng)論0 收藏0

  • [LintCode] Remove Node in Binary Search Tree [理解BS

    Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...

    陳江龍 評(píng)論0 收藏0

  • [LintCode] Insert Node in a Binary Search Tree

    摘要：建立兩個(gè)樹結(jié)點(diǎn)，先用找到在的位置，讓作為的根節(jié)點(diǎn)找到的位置后，指向。此時(shí)，用代替與連接就可以了。 Problem Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tr...

    Taste 評(píng)論0 收藏0

  • leetcode98. Validate Binary Search Tree

    摘要：題目要求檢驗(yàn)二叉查找樹是否符合規(guī)則。二叉查找樹是指當(dāng)前節(jié)點(diǎn)左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實(shí)現(xiàn)中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規(guī)則。 題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

    codercao 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<