LeetCode Day 17 binary tree (4/9)
Published:
Still focus on binary tree.
Question 1
Given a binary tree, determine if it is height-balanced
height-balanced is defined as a binary tree in which the difference in height between the left and right subtrees is no more than one.
Since we are comparing heights, we need to do a backward traversal.
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
height_map = {}
stack = [root]
while stack:
node = stack.pop()
if node:
stack.append(node)
stack.append(None)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
else:
real_node = stack.pop()
left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0)
if abs(left - right) > 1:
return False
height_map[real_node] = 1 + max(left, right)
return True
Question 2
Given the
rootof a binary tree, return all root-to-leaf paths in any order.A leaf is a node with no children.
This question involves backtracking, because we want to record the paths, and we need to backtrack to go back one path and enter another.
It also has to be combined with recursion, recursion and backtracking are supposed to be in the same family
class Solution:
def traversal(self, cur, path, result):
path.append(cur.val)
if not cur.left and not cur.right:
sPath = '->'.join(map(str, path))
result.append(sPath)
return
if cur.left:
self.traversal(cur.left, path, result)
path.pop()
if cur.right:
self.traversal(cur.right, path, result)
path.pop()
def binaryTreePaths(self, root):
result = []
path = []
if not root:
return result
self.traversal(root, path, result)
return result
Question 3
Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Post-order traversal using recursion
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
if root.left is None and root.right is None:
return 0
leftValue = self.sumOfLeftLeaves(root.left)
if root.left and not root.left.left and not root.left.right:
leftValue = root.left.val
rightValue = self.sumOfLeftLeaves(root.right)
sum_val = leftValue + rightValue
return sum_val