99. Recover Binary Search Tree

superw 发布于2019-08-14 14:14 / 1576人阅读

摘要：题目解答想法很简单，找到两个顺序不对的点，交换。但是如何知道这两个点的顺序是不对的呢因为是左中右，所以我们可以用的方法模板代码如下

题目：
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?

解答：
想法很简单，找到两个顺序不对的点，交换。但是如何知道这两个点的顺序是不对的呢？因为BST是左<中<右，所以我们可以用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);
    }
}

GPU云服务器云服务器 binary-search-tree binary-tree binary-search recover

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

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

leetcode 315 Count of Smaller Numbers After Self 以

摘要：题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来，最后回原来正确的值。如果是叶子节点，或者只有一个子树。思想来自于的代码实现。跳过总结请点这里：https://segmentfault.com/a/11... BST最明显的特点就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 评论0 收藏0
Inorder Preorder Postorder

摘要：题目链接参考这篇文章链接题目链接还是一样的，用，或者保存和。题目链接题目链接按照的顺序最后再一下。 Inorder Binary Tree Inorder Traversal lc题目链接：https://leetcode.com/problems... recursion： public class Solution { public List inorderTraversa...

caikeal 2019-08-14 17:23 评论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...

陈江龙 2019-08-14 15:33 评论0 收藏0
[LintCode] Insert Node in a Binary Search Tree

摘要：建立两个树结点，先用找到在的位置，让作为的根节点找到的位置后，指向。此时，用代替与连接就可以了。 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 2019-08-14 15:33 评论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