LeetCode Day 15 binary tree (2/9)
Published:
The second day of binary tree, questions are not difficult, but But it’s important to have clear mind of these quesions.
Question 1
102. Binary Tree Level Order Traversal
Given the
rootof a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Yesterday, when I was sorting out the basics, I mentioned that hierarchical traversal is a type of breadth-first traversal.
The solution to this problem uses a queue, along with a variable to keep track of how many numbers are in each layer, so as to ensure that when you come out of the queue, you distinguish how many are in each layer.
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = collections.deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
cur = queue.popleft()
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
result.append(level)
return result
Question 2
Pre-order traversal and post-order traversal are fine for this question, except for mid-order traversal, which is inconvenient because of the possibility of inverting some nodes twice
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
Question 3
Given the
rootof a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
For this question, we are actually comparing two trees (which are the left and right subtrees of the root node)
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
st = []
st.append(root.left)
st.append(root.right)
while st:
rightNode = st.pop()
leftNode = st.pop()
if not leftNode and not rightNode:
continue
if not leftNode or not rightNode or leftNode.val != rightNode.val:
return False
st.append(leftNode.left)
st.append(rightNode.right)
st.append(leftNode.right)
st.append(rightNode.left)
return True