_1660. Correct a Binary Tree.md

1660. Correct a Binary Tree

Back to top

---

First completed : June 26, 2024

Last updated : June 26, 2024

---

Related Topics : Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Acceptance Rate : 74.384 %

---

To see the question prompt, click the title.

Solutions

• m1660 v1.py
• m1660 v2 One Pass.py

Python

m1660 v1.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def correctBinaryTree(self, root: TreeNode) -> TreeNode:
        toVisit = [(root, 0)]       # (curr, depth)
        depths = {}

        while toVisit :
            curr, depth = toVisit.pop()
            if not curr :
                continue
            if curr in depths and depths[curr] < depth :
                continue

            depths[curr] = depth
            depth += 1

            toVisit.append((curr.left, depth))
            toVisit.append((curr.right, depth))

        toVisit.append((root))

        while toVisit :
            parent = toVisit.pop()

            if parent.left and \
                    ((parent.left.left and depths[parent.left] == depths[parent.left.left]) or \
                    (parent.left.right and depths[parent.left] == depths[parent.left.right])) :
                parent.left = None
                break

            if parent.right and \
                    ((parent.right.right and depths[parent.right] == depths[parent.right.right]) or \
                    (parent.right.left and depths[parent.right] == depths[parent.right.left])) :
                parent.right = None
                break
            
            if parent.right :
                toVisit.append(parent.right)
            if parent.left :
                toVisit.append(parent.left)


        return root

m1660 v2 One Pass.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def correctBinaryTree(self, root: TreeNode) -> TreeNode:
        toVisit = [(root, None, 0)]       # (curr, depth)
        depths = {}

        while toVisit :
            curr, parent, depth = toVisit.pop()
            if not curr :
                continue

            if curr.left in depths or curr.right in depths :
                if parent.left == curr :
                    parent.left = None
                else :
                    parent.right = None
                break
            
            depths[curr] = depth
            depth += 1

            toVisit.append((curr.left, curr, depth))
            toVisit.append((curr.right, curr, depth))
            
        return root