LeetCode Day 18 binary tree (5/9)
Published:
Reached half, go for it!
Question 1
513. Find Bottom Left Tree Value
Given the
rootof a binary tree, return the leftmost value in the last row of the tree.
Just traverse in hierarchical order and look for the left node.
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
queue = deque()
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == 0:
result = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Question 2
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node,s):
if not node:
return
s += (node.val)
if node.left is None and node.right is None:
if s == targetSum:
return True
return dfs(node.left,s) or dfs(node.right,s)
return dfs(root,0)
Question 3
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Use iteration method
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
stack = [(root, [root.val])]
res = []
while stack:
node, path = stack.pop()
if not node.left and not node.right and sum(path) == targetSum:
res.append(path)
if node.right:
stack.append((node.right, path + [node.right.val]))
if node.left:
stack.append((node.left, path + [node.left.val]))
return res
Question 4
106. Construct Binary Tree from Inorder and Postorder Traversal
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
It can be solved with recursion method
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
separator_idx = inorder.index(root_val)
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left): len(postorder) - 1]
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
return root
Question 5
105. Construct Binary Tree from Preorder and Inorder Traversal
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
The idea is similar to the previous question, still using the recursive method
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
separator_idx = inorder.index(root_val)
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
preorder_left = preorder[1:1 + len(inorder_left)]
preorder_right = preorder[1 + len(inorder_left):]
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
return root