Binary Tree Postorder Traversal
Given the root of a binary tree, return the postorder traversal of its nodes' values.
# recursive
def postorderTraversal1(self, root):
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root:
self.dfs(root.left, res)
self.dfs(root.right, res)
res.append(root.val)
# iterative
def postorderTraversal(self, root):
res, stack = [], [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.left)
stack.append(node.right)
return res[::-1]Related Problems
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Given the root of a binary tree, invert the tree, and return its root.
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtreeof a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.