94. Binary Tree Inorder Traversal
题目:
https://leetcode.com/problems/binary-tree-inorder-traversal/
难度:
Medium
递归
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.lst = []
self.DFS(root)
return self.lst
def DFS(self,root):
if root == None:
return
if root.left:
self.DFS(root.left)
self.lst.append(root.val)
if root.right:
self.DFS(root.right)
非递归用stack，我听谁讲过 😓
// to be done
via wikipedia
递归：
inorder(node)
if (node = null)
return
inorder(node.left)
visit(node)
inorder(node.right)
非递归,跟之前那个iterator有得一拼，其实好几个题都是在玩这个花样？
iterativeInorder(node)
s ← empty stack
while (not s.isEmpty() or node ≠ null)
if (node ≠ null)
s.push(node)
node ← node.left
else
node ← s.pop()
visit(node)
node ← node.right
