Description (Inorder, 94):
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
2
/
3Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
Solutions:
Trivial solution:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
Runtime: 36 ms, faster than 67.60% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.1 MB, less than 70.72% of Python3 online submissions for Binary Tree Inorder Traversal.
None-trivial solution:
NOTE:
Maintain a stack, push root first, then every iteration, push left child first if existed.
If a left child is searched, result.append(current_parent_node's value), and left child = None, and search right child.
If a right child is searched, pop until a left child shows up.
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
stack = [[root,True]]
result = []
while stack:
# print('\n--------------------------------')
# print(result)
# for s in stack:
# print(s[0].val,s[1])
cmp1 = stack[-1][0].left != None
cmp2 = stack[-1][0].right != None
if not cmp1 and not cmp2:
result.append(stack[-1][0].val)
left_or_right = stack[-1][1]
stack.pop()
while True:
if left_or_right == False:
stack[-1][0].left = None
break
if not stack:
break
else:
# stack[-1][0].right = None
left_or_right = stack[-1][1]
stack.pop()
elif cmp1:
stack.append([stack[-1][0].left,False])
# stack 0th element is Node, 1st element is False if it's a left Node
elif cmp2:
result.append(stack[-1][0].val)
stack.append([stack[-1][0].right,True])
# 1st element is False if it's a right Node
return result
Runtime: 32 ms, faster than 88.81% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.2 MB, less than 62.47% of Python3 online submissions for Binary Tree Inorder Traversal.
Better solution
inspired by https://zhuanlan.zhihu.com/p/65795759 and https://www.cnblogs.com/grandyang/p/4297300.html解法3
NOTE:
只要当前节点（stack[-1]）不是None，就继续左转。如果是None，则先pop去掉最后一个None，然后保存最后一个元素（非None），继续pop这个元素，并把这个元素的right push进栈。
先左转保证“left”在顺序的最前面，“继续pop这个元素”是把parent放到顺序的第二位，再把right push进栈说明right child在顺序的最后。
链接里面的方法是建立一个curr一直等于当前搜索到的节点。如果是None就不push进栈，也就避免了pop两次
这种方法的精髓是，在遍历right child的时候，parent已经在stack中pop掉了，那如果right child遍历完成之后，关于right child下的节点都不会在stack里面，stack[-1]就是grandparent了。那么就不用要求node本身保存一个变量记住顺序，也不用单独在循环里保存一个True or False来记录之前左右转的历史情况。
# Code according to my understanding
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
stack = [root]
result = []
while stack:
if stack[-1] != None:
stack.append(stack[-1].left)
else:
stack.pop()
if stack: # prevent the last step of traversal requiring to pop a empty stack
cache = stack.pop()
result.append(cache.val)
stack.append(cache.right)
return result
Runtime: 28 ms, faster than 97.62% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 12.9 MB, less than 99.69% of Python3 online submissions for Binary Tree Inorder Traversal.
# rewrite the source code in Zhihu
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
result = []
curr = root
while curr != None or stack:
if curr != None:
stack.append(curr)
curr = curr.left
else:
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
Description (Preorder, 144):
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
Solutions:
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
Runtime: 32 ms, faster than 89.16% of Python3 online submissions for Binary Tree Preorder Traversal.
Memory Usage: 13.1 MB, less than 64.36% of Python3 online submissions for Binary Tree Preorder Traversal.
inspired by https://www.cnblogs.com/grandyang/p/4146981.html
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
ret = []
stack = []
curr = root
while curr != None or stack:
if curr != None:
stack.append(curr)
ret.append(curr.val) # moved from the "else" code block to the "if" code block
curr = curr.left
else:
curr = stack.pop().right
return ret
Runtime: 32 ms, faster than 89.16% of Python3 online submissions for Binary Tree Preorder Traversal.
Memory Usage: 13.1 MB, less than 83.48% of Python3 online submissions for Binary Tree Preorder Traversal.
Description (Postorder, 145):
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
Solutions:
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
Runtime: 36 ms, faster than 66.25% of Python3 online submissions for Binary Tree Postorder Traversal.
Memory Usage: 13.2 MB, less than 43.46% of Python3 online submissions for Binary Tree Postorder Traversal.
花了4个小时搞出来的野路子Solution：
NOTE:
每次到一个新的节点了，stack push进右child和左child，但如果这俩都是None的话，就pop出stack元素，直到stack[-2]不是stack[-1]的parent，那么就继续pop一次，把当前这个子树都pop完，之后curr就成了下一个子树的父节点。
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
if root.left == None and root.right == None:
return [root.val]
ret = []
stack = [root]
curr = root
while curr != None or stack:
if curr != None:
if curr.right != None:
stack.append(curr.right)
if curr.left != None:
stack.append(curr.left)
if curr != stack[-1]:
curr = stack[-1]
else:
while len(stack) > 1 and (stack[-2].left == curr or stack[-2].right == curr):
ret.append(stack.pop().val)
curr = stack[-1]
ret.append(stack.pop().val)
if not stack:
break
curr = stack[-1]
return ret
Runtime: 36 ms, faster than 66.25% of Python3 online submissions for Binary Tree Postorder Traversal.
Memory Usage: 13.2 MB, less than 56.25% of Python3 online submissions for Binary Tree Postorder Traversal.
Solution: 重新写先序遍历的时候想到的，通过对stack这个数组进行操作的一种新方法
inspired by https://www.cnblogs.com/grandyang/p/4251757.html
由于后序遍历的顺序是左-右-根，而先序遍历的顺序是根-左-右，二者其实还是很相近的，我们可以先在先序遍历的方法上做些小改动，使其遍历顺序变为根-右-左，然后翻转一下，就是左-右-根啦
# 后序遍历
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
ret = []
stack = [root]
curr = root
while curr != None or stack:
if curr != None:
ret.append(curr.val)
stack.pop()
stack += [curr.left,curr.right]
curr = curr.right
else:
stack.pop()
if not stack:
break
curr = stack[-1]
return ret[::-1]
# 先序遍历
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
ret = []
stack = [root]
curr = root
while curr != None or stack:
if curr != None:
ret.append(curr.val)
stack.pop()
stack += [curr.right,curr.left] # left right 交换
curr = curr.left # left right 交换
else:
stack.pop()
if not stack:
break
curr = stack[-1]
return ret
# 中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
ret = []
stack = [root]
curr = root
while curr != None or stack:
if curr != None:
stack.pop()
stack += [curr.right,curr,curr.left]
curr = curr.left
else:
if len(stack) == 1:
break
ret.append(stack[-2].val)
stack.pop()
stack.pop()
curr = stack[-1]
return ret
Morris inorder traversal:
inspired by https://www.youtube.com/watch?v=wGXB9OWhPTg and
https://www.cnblogs.com/anniekim/archive/2013/06/15/morristraversal.html
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
ret = []
curr = root
def FindPredecessor(node): # missing part of the picture
cache = node.left
while cache.right != None and cache.right != node:
# searching predecessor for the second time will finally turn back to node itself => "and cache.right != node"
cache = cache.right
return cache
while curr != None:
if curr.left == None:
# 左边是空，那么就pop，但是下一步可能往父节点的右边走，也可能父节点没有右边，则只需要回到父节点。
# 这里巧妙地把两种情况都先赋予了curr.right。
ret.append(curr.val)
curr = curr.right
else:
pred = FindPredecessor(curr)
if pred.right == None: # 如果是第一次遍历到这个node
pred.right = curr
curr = curr.left
# elif pred.right == curr: # 如果已经遍历过这个node
else:
pred.right = None
ret.append(curr.val)
curr = curr.right
return ret
Runtime: 20 ms, faster than 99.99% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.2 MB, less than 44.95% of Python3 online submissions for Binary Tree Inorder Traversal.
Morris preorder traversal:
NOTE: 第一反应是把pred.right赋予curr.right，但是想了半天也没发现如何知道是否在移动到右侧的时候要把前置node.right归None。然后看了下https://www.geeksforgeeks.org/morris-traversal-for-preorder/
发现正确的搜索顺序和上面inorder一样，只需要把添加父节点的时间提前。
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
ret = []
curr = root
def FindPredecessor(node): # the same
cache = node.left
while cache.right != None and cache.right != node:
cache = cache.right
return cache
while curr != None:
if curr.left == None: # the same
ret.append(curr.val)
curr = curr.right
else:
pred = FindPredecessor(curr)
if pred.right == None: # first time to meet a parent node
ret.append(curr.val) # moved from "else"
pred.right = curr
curr = curr.left
else: # second time to meet, meaning that it's a searched node
curr = curr.right
pred.right = None
return ret
Runtime: 36 ms, faster than 66.49% of Python3 online submissions for Binary Tree Preorder Traversal.
Memory Usage: 13.3 MB, less than 7.02% of Python3 online submissions for Binary Tree Preorder Traversal.
Morris postorder traversal:
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
curr = root
ret = []
def FindPredecessor(node):
cache = node.right
while cache.left != None and cache.left != node:
cache = cache.left
return cache
while curr != None:
if curr.right == None:
ret.append(curr.val)
curr = curr.left
else:
pred = FindPredecessor(curr)
if pred.left == None:
pred.left = curr
ret.append(curr.val)
curr = curr.right
else:
curr = curr.left
pred.left = None
return ret[::-1]
