Python Inorder Traversal solution based on Validate Binary Search Tree


  • 4
    T
    class Solution:
    # @param root, a tree node
    # @return a tree node
    def recoverTree(self, root):
        it = self.isValidBST(root)
        a, b = next(it)
        c = next(it, None)
        if c:
            _, c = c
            a.val, c.val = c.val, a.val
        else:
            a.val, b.val = b.val, a.val
        return root
    
    def isValidBST(self, root):
        pre, cur, stack = None, root, []
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            s = stack.pop()
            if pre and s.val <= pre.val:
                yield pre, s
            pre, cur = s, s.right
    

    This is a simple O(n) space solution.

    Add Java solution

    TreeNode prev = null;
    LinkedList<TreeNode> result = new LinkedList<TreeNode>();
    
    public void recoverTree(TreeNode root) {
        isValidBST(root);
        TreeNode first = result.poll();
        TreeNode last = result.pollLast();
        int temp = first.val;
        first.val = last.val;
        last.val = temp;
    }
    
    private void isValidBST(TreeNode root) {
        if (root == null)
            return;
        isValidBST(root.left);
        if (prev != null && root.val < prev.val) {
            result.add(prev);
            result.add(root);
        }
        prev = root;
        isValidBST(root.right);
    }

  • 0
    S

    It's a great solution! It helped me understand python's way of recursion. There is only a minor mistake. Since the question does not require any return value, you should remove the "return root" in recovertree().


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.