Solution to LeetCode 94 Binary Tree Inorder Traversal, LeetCode 144 Binary Tree Preorder Traversal, LeetCode 145 Binary Tree Postorder Traversal, and LeetCode 102 Binary Tree Level Order Traversal.
LeetCode 94
Binary Tree Inorder Traversal. (Easy) [link]
Recursive traversal. Time complexity O(n).
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def traversal(root):
if root == None:
return
traversal(root.left)
res.append(root.val)
traversal(root.right)
traversal(root)
return res
Iterative traversal by Stack. Time complexity O(n).
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
stack = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
LeetCode 144
Binary Tree Preorder Traversal. (Easy) [link]
Recursive Traversal. Time complexity O(n).
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def traversal(root):
if root == None:
return
res.append(root.val)
traversal(root.left)
traversal(root.right)
traversal(root)
return res
Iterative Traversal by Stack. Right child first in so that left child first out. Time complexity O(n).
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
if not root:
return res
stack = [root]
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return res
LeetCode 145
Binary Tree Postorder Traversal (Easy) [link]
Recursive Traversal. Time complexity O(n).
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def traversal(root):
if root == None:
return
traversal(root.left)
traversal(root.right)
res.append(root.val)
traversal(root)
return res
Iterative Traversal by Stack. This is a reverse of getting preorder. Time complexity O(n).
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
if not root: return res
stack = [root]
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.left:
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
return res[::-1]
LeetCode 102
Binary Tree Level Order Traversal (Medium). [link]
Level-order traversal.
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
que = deque([root])
results = []
if not root: return results
while que:
res = []
size = len(que)
for i in range(size):
cur = que.popleft()
res.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
results.append(res)
return results
Similar: LeetCode 107 Binary Tree Level Order Traversal II, LeetCode 199 Binary Tree Right Side View, LeetCode 637 Average of Levels in Binary Tree, LeetCode 429 N-ary Tree Level Order Traversal, LeetCode 515 Find Largest Value in Each Tree Row, LeetCode 116 Populating Next Right Pointers in Each Node, LeetCode 117 Populating Next Right Pointers in Each Node II, LeetCode 104 Maximum Depth of Binary Tree, LeetCode 111 Minimum Depth of Binary Tree.
