144. 二叉树的前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

# Definition for a binary tree node. class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] result = [] stack = [root] # 需要一个标志区分每个递归调用栈，这里使用null来表示 while stack: p = stack.pop() # 访问过的节点弹出 if p is None: # 空节点表示之前已经访问过了，现在需要处理除了递归之外的内容 p = stack.pop() # 处理完了，第二次弹出节点（彻底从栈中移除） result.append(p.val) # 此时p是null之前压栈的一个节点，也就是上面stack.append(p)中的那个p else: if p.right: # 右节点先压栈，最后处理 stack.append(p.right) # 先append的最后访问 if p.left: stack.append(p.left) stack.append(p) # 当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈 stack.append(None) # 在当前节点之前加入一个空节点表示已经访问过了 return result

顺序：根左右

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = [] if not root: return res stack = [root] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = [] def helper(root): if not root: return res.append(root.val) helper(root.left) helper(root.right) helper(root) return res

94. 二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

# Definition for a binary tree node. class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] result = [] stack = [root] # 需要一个标志区分每个递归调用栈，这里使用null来表示 while stack: p = stack.pop() # 访问过的节点弹出 if p is None: # 空节点表示之前已经访问过了，现在需要处理除了递归之外的内容 p = stack.pop() # 处理完了，第二次弹出节点（彻底从栈中移除） result.append(p.val) # 此时p是null之前压栈的一个节点，也就是上面stack.append(p)中的那个p else: if p.right: # 右节点先压栈，最后处理 stack.append(p.right) # 先append的最后访问 stack.append(p) # 当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈 stack.append(None) # 在当前节点之前加入一个空节点表示已经访问过了 if p.left: stack.append(p.left) return result

顺序：左根右

迭代:用栈,再用一个指针模拟访问过程

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [] # 用p当做指针 p = root while p or stack: # 把左子树压入栈中 while p: stack.append(p) p = p.left # 输出 栈顶元素 p = stack.pop() res.append(p.val) # 看右子树 p = p.right return res class Solution: def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ res = [] def helper(root): if not root: return helper(root.left) res.append(root.val) helper(root.right) helper(root) return res

 

145. 二叉树的后序遍历 

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

# Definition for a binary tree node. class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] result = [] stack = [root] # 需要一个标志区分每个递归调用栈，这里使用null来表示 while stack: p = stack.pop() # 访问过的节点弹出 if p is None: # 空节点表示之前已经访问过了，现在需要处理除了递归之外的内容 p = stack.pop() # 处理完了，第二次弹出节点（彻底从栈中移除） result.append(p.val) # 此时p是null之前压栈的一个节点，也就是上面stack.append(p)中的那个p else: stack.append(p) # 当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈 stack.append(None) # 在当前节点之前加入一个空节点表示已经访问过了 if p.right: # 右节点先压栈，最后处理 stack.append(p.right) # 先append的最后访问 if p.left: stack.append(p.left) return result

递归:顺序:左,右,根  

迭代:和上面的先序一样,我们可以改变入栈的顺序,刚才先序是从右到左,我们这次从左到右,最后得到的结果取逆. 

class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: res = [] if not root: return res stack = [root] while stack: node = stack.pop() if node.left : stack.append(node.left) if node.right: stack.append(node.right) res.append(node.val) return res[::-1] class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: res = [] def helper(root): if not root: return helper(root.left) helper(root.right) res.append(root.val) helper(root) return res

参考题解

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/mo-fang-di-gui-zhi-bian-yi-xing-by-sonp/

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-he-di-gui-by-powcai/