Leetcode: Recover Binary Search Tree

Recover Binary Search Tree


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?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/recover-binary-search-tree
## Basic Ideas:
##              It could be left-right swap or parent-child swap
##              It could also be two non-adjacent nodes
##              Identity the node. Then swap the value
##  Assumption: Whether the tree contains duplicates?
## Complexity:
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if root is None:
            return
        # level tree trasversal
        queue = []
        queue.append(root)
        while len(queue) != 0:
            for i in xrange(len(queue)):
                node = queue[0]
                del queue[0]
                # issue of left-right
                if node.left and node.right and node.left.val > node.right.val:
                    node.left.val, node.right.val = node.right.val, node.left.val
                    return
                # issue of parent-child
                if node.left and node.val < node.left.val:
                    node.val, node.left.val = node.left.val, node.val
                    return
                if node.right and node.val > node.right.val:
                    node.val, node.right.val = node.right.val, node.val
                    return
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.