二叉树的迭代遍历 - 图1
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

二叉树的迭代遍历

听说还可以用非递归的方式

看完本篇大家可以使用迭代法，再重新解决如下三道leetcode上的题目：

  • 144.二叉树的前序遍历
  • 94.二叉树的中序遍历
  • 145.二叉树的后序遍历

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

我们在栈与队列：匹配问题都是栈的强项中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

前序遍历（迭代法）

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

动画如下：

二叉树的迭代遍历 - 图2

不难写出如下代码: （注意代码中空节点不入栈）

  1. class Solution {
  2. public:
  3.     vector<int> preorderTraversal(TreeNode* root) {
  4.         stack<TreeNode*> st;
  5.         vector<int> result;
  6.         if (root == NULL) return result;
  7.         st.push(root);
  8.         while (!st.empty()) {
  9.             TreeNode* node = st.top();                       // 中
  10.             st.pop();
  11.             result.push_back(node->val);
  12.             if (node->right) st.push(node->right);           // 右（空节点不入栈）
  13.             if (node->left) st.push(node->left);             // 左（空节点不入栈）
  14.         }
  15.         return result;
  16.     }
  17. };

此时会发现貌似使用迭代法写出前序遍历并不难，确实不难。

此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了？

其实还真不行！

但接下来，再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。

中序遍历（迭代法）

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

动画如下：

二叉树的迭代遍历 - 图3

中序遍历，可以写出如下代码：

  1. class Solution {
  2. public:
  3.     vector<int> inorderTraversal(TreeNode* root) {
  4.         vector<int> result;
  5.         stack<TreeNode*> st;
  6.         TreeNode* cur = root;
  7.         while (cur != NULL || !st.empty()) {
  8.             if (cur != NULL) { // 指针来访问节点，访问到最底层
  9.                 st.push(cur); // 将访问的节点放进栈
  10.                 cur = cur->left;                // 左
  11.             } else {
  12.                 cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
  13.                 st.pop();
  14.                 result.push_back(cur->val);     // 中
  15.                 cur = cur->right;               // 右
  16.             }
  17.         }
  18.         return result;
  19.     }
  20. };

后序遍历（迭代法）

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

二叉树的迭代遍历 - 图4

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root) {
  4.         stack<TreeNode*> st;
  5.         vector<int> result;
  6.         if (root == NULL) return result;
  7.         st.push(root);
  8.         while (!st.empty()) {
  9.             TreeNode* node = st.top();
  10.             st.pop();
  11.             result.push_back(node->val);
  12.             if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
  13.             if (node->right) st.push(node->right); // 空节点不入栈
  14.         }
  15.         reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
  16.         return result;
  17.     }
  18. };

总结

此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不像递归写法那样代码稍做调整，就可以实现前后中序。

这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

上面这句话，可能一些同学不太理解，建议自己亲手用迭代法，先写出来前序，再试试能不能写出中序，就能理解了。

那么问题又来了，难道 二叉树前后中序遍历的迭代法实现，就不能风格统一么（即前序遍历 改变代码顺序就可以实现中序 和 后序）？

当然可以，这种写法，还不是很好理解，我们将在下一篇文章里重点讲解，敬请期待！

其他语言版本

Java：

  1. // 前序遍历顺序：中-左-右，入栈顺序：中-右-左
  2. class Solution {
  3.     public List<Integer> preorderTraversal(TreeNode root) {
  4.         List<Integer> result = new ArrayList<>();
  5.         if (root == null){
  6.             return result;
  7.         }
  8.         Stack<TreeNode> stack = new Stack<>();
  9.         stack.push(root);
  10.         while (!stack.isEmpty()){
  11.             TreeNode node = stack.pop();
  12.             result.add(node.val);
  13.             if (node.right != null){
  14.                 stack.push(node.right);
  15.             }
  16.             if (node.left != null){
  17.                 stack.push(node.left);
  18.             }
  19.         }
  20.         return result;
  21.     }
  22. }
  24. // 中序遍历顺序: 左-中-右 入栈顺序： 左-右
  25. class Solution {
  26.     public List<Integer> inorderTraversal(TreeNode root) {
  27.         List<Integer> result = new ArrayList<>();
  28.         if (root == null){
  29.             return result;
  30.         }
  31.         Stack<TreeNode> stack = new Stack<>();
  32.         TreeNode cur = root;
  33.         while (cur != null || !stack.isEmpty()){
  34.            if (cur != null){
  35.                stack.push(cur);
  36.                cur = cur.left;
  37.            }else{
  38.                cur = stack.pop();
  39.                result.add(cur.val);
  40.                cur = cur.right;
  41.            }
  42.         }
  43.         return result;
  44.     }
  45. }
  47. // 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
  48. class Solution {
  49.     public List<Integer> postorderTraversal(TreeNode root) {
  50.         List<Integer> result = new ArrayList<>();
  51.         if (root == null){
  52.             return result;
  53.         }
  54.         Stack<TreeNode> stack = new Stack<>();
  55.         stack.push(root);
  56.         while (!stack.isEmpty()){
  57.             TreeNode node = stack.pop();
  58.             result.add(node.val);
  59.             if (node.left != null){
  60.                 stack.push(node.left);
  61.             }
  62.             if (node.right != null){
  63.                 stack.push(node.right);
  64.             }
  65.         }
  66.         Collections.reverse(result);
  67.         return result;
  68.     }
  69. }

Python：

  1. # 前序遍历-迭代-LC144_二叉树的前序遍历
  2. class Solution:
  3.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  4.         # 根结点为空则返回空列表
  5.         if not root:
  6.             return []
  7.         stack = [root]
  8.         result = []
  9.         while stack:
  10.             node = stack.pop()
  11.             # 中结点先处理
  12.             result.append(node.val)
  13.             # 右孩子先入栈
  14.             if node.right:
  15.                 stack.append(node.right)
  16.             # 左孩子后入栈
  17.             if node.left:
  18.                 stack.append(node.left)
  19.         return result
  21. # 中序遍历-迭代-LC94_二叉树的中序遍历
  22. class Solution:
  23.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  24.         if not root:
  25.             return []
  26.         stack = []  # 不能提前将root结点加入stack中
  27.         result = []
  28.         cur = root
  29.         while cur or stack:
  30.             # 先迭代访问最底层的左子树结点
  31.             if cur:     
  32.                 stack.append(cur)
  33.                 cur = cur.left        
  34.             # 到达最左结点后处理栈顶结点    
  35.             else:        
  36.                 cur = stack.pop()
  37.                 result.append(cur.val)
  38.                 # 取栈顶元素右结点
  39.                 cur = cur.right    
  40.         return result
  42. # 后序遍历-迭代-LC145_二叉树的后序遍历
  43. class Solution:
  44.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  45.         if not root:
  46.             return []
  47.         stack = [root]
  48.         result = []
  49.         while stack:
  50.             node = stack.pop()
  51.             # 中结点先处理
  52.             result.append(node.val)
  53.             # 左孩子先入栈
  54.             if node.left:
  55.                 stack.append(node.left)
  56.             # 右孩子后入栈
  57.             if node.right:
  58.                 stack.append(node.right)
  59.         # 将最终的数组翻转
  60.         return result[::-1]

Go：

迭代法前序遍历

  1. func preorderTraversal(root *TreeNode) []int {
  2.     ans := []int{}
  4.     if root == nil {
  5.         return ans
  6.     }
  8.     st := list.New()
  9.     st.PushBack(root)
  11.     for st.Len() > 0 {
  12.         node := st.Remove(st.Back()).(*TreeNode)
  14.         ans = append(ans, node.Val)
  15.         if node.Right != nil {
  16.             st.PushBack(node.Right)
  17.         }
  18.         if node.Left != nil {
  19.             st.PushBack(node.Left)
  20.         }
  21.     }
  22.     return ans
  23. }

迭代法后序遍历

  1. func postorderTraversal(root *TreeNode) []int {
  2.     ans := []int{}
  4.     if root == nil {
  5.         return ans
  6.     }
  8.     st := list.New()
  9.     st.PushBack(root)
  11.     for st.Len() > 0 {
  12.         node := st.Remove(st.Back()).(*TreeNode)
  14.         ans = append(ans, node.Val)
  15.         if node.Left != nil {
  16.             st.PushBack(node.Left)
  17.         }
  18.         if node.Right != nil {
  19.             st.PushBack(node.Right)
  20.         }
  21.     }
  22.     reverse(ans)
  23.     return ans
  24. }
  26. func reverse(a []int) {
  27.     l, r := 0, len(a) - 1
  28.     for l < r {
  29.         a[l], a[r] = a[r], a[l]
  30.         l, r = l+1, r-1
  31.     }
  32. }

迭代法中序遍历

  1. func inorderTraversal(root *TreeNode) []int {
  2.     ans := []int{}
  3.     if root == nil {
  4.         return ans
  5.     }
  7.     st := list.New()
  8.     cur := root
  10.     for cur != nil || st.Len() > 0 {
  11.         if cur != nil {
  12.             st.PushBack(cur)
  13.             cur = cur.Left
  14.         } else {
  15.             cur = st.Remove(st.Back()).(*TreeNode)
  16.             ans = append(ans, cur.Val)
  17.             cur = cur.Right
  18.         }
  19.     }
  21.     return ans
  22. }

javaScript：

  2. 前序遍历:
  4. // 入栈 右 -> 左
  5. // 出栈 中 -> 左 -> 右
  6. var preorderTraversal = function(root, res = []) {
  7.     if(!root) return res;
  8.     const stack = [root];
  9.     let cur = null;
  10.     while(stack.length) {
  11.         cur = stack.pop();
  12.         res.push(cur.val);
  13.         cur.right && stack.push(cur.right);
  14.         cur.left && stack.push(cur.left);
  15.     }
  16.     return res;
  17. };
  19. 中序遍历:
  21. // 入栈 左 -> 右
  22. // 出栈 左 -> 中 -> 右
  24. var inorderTraversal = function(root, res = []) {
  25.     const stack = [];
  26.     let cur = root;
  27.     while(stack.length || cur) {
  28.         if(cur) {
  29.             stack.push(cur);
  30.             // 左
  31.             cur = cur.left;
  32.         } else {
  33.             // --> 弹出 中
  34.             cur = stack.pop();
  35.             res.push(cur.val); 
  36.             // 右
  37.             cur = cur.right;
  38.         }
  39.     };
  40.     return res;
  41. };
  43. 后序遍历:
  45. // 入栈 左 -> 右
  46. // 出栈 中 -> 右 -> 左 结果翻转
  48. var postorderTraversal = function(root, res = []) {
  49.     if (!root) return res;
  50.     const stack = [root];
  51.     let cur = null;
  52.     do {
  53.         cur = stack.pop();
  54.         res.push(cur.val);
  55.         cur.left && stack.push(cur.left);
  56.         cur.right && stack.push(cur.right);
  57.     } while(stack.length);
  58.     return res.reverse();
  59. };

TypeScript：

  1. // 前序遍历（迭代法）
  2. function preorderTraversal(root: TreeNode | null): number[] {
  3.     if (root === null) return [];
  4.     let res: number[] = [];
  5.     let helperStack: TreeNode[] = [];
  6.     let curNode: TreeNode = root;
  7.     helperStack.push(curNode);
  8.     while (helperStack.length > 0) {
  9.         curNode = helperStack.pop()!;
  10.         res.push(curNode.val);
  11.         if (curNode.right !== null) helperStack.push(curNode.right);
  12.         if (curNode.left !== null) helperStack.push(curNode.left);
  13.     }
  14.     return res;
  15. };
  17. // 中序遍历（迭代法）
  18. function inorderTraversal(root: TreeNode | null): number[] {
  19.     let helperStack: TreeNode[] = [];
  20.     let res: number[] = [];
  21.     if (root === null) return res;
  22.     let curNode: TreeNode | null = root;
  23.     while (curNode !== null || helperStack.length > 0) {
  24.         if (curNode !== null) {
  25.             helperStack.push(curNode);
  26.             curNode = curNode.left;
  27.         } else {
  28.             curNode = helperStack.pop()!;
  29.             res.push(curNode.val);
  30.             curNode = curNode.right;
  31.         }
  32.     }
  33.     return res;
  34. };
  36. // 后序遍历（迭代法）
  37. function postorderTraversal(root: TreeNode | null): number[] {
  38.     let helperStack: TreeNode[] = [];
  39.     let res: number[] = [];
  40.     let curNode: TreeNode;
  41.     if (root === null) return res;
  42.     helperStack.push(root);
  43.     while (helperStack.length > 0) {
  44.         curNode = helperStack.pop()!;
  45.         res.push(curNode.val);
  46.         if (curNode.left !== null) helperStack.push(curNode.left);
  47.         if (curNode.right !== null) helperStack.push(curNode.right);
  48.     }
  49.     return res.reverse();
  50. };

Swift：

  1. // 前序遍历迭代法
  2. func preorderTraversal(_ root: TreeNode?) -> [Int] {
  3.     var result = [Int]()
  4.     guard let root = root else { return result }
  5.     var stack = [root]
  6.     while !stack.isEmpty {
  7.         let current = stack.removeLast()
  8.         // 先右后左，这样出栈的时候才是左右顺序
  9.         if let node = current.right { // 右
  10.             stack.append(node)
  11.         }
  12.         if let node = current.left { // 左
  13.             stack.append(node)
  14.         }
  15.         result.append(current.val) // 中
  16.     }
  17.     return result
  18. }
  20. // 后序遍历迭代法
  21. func postorderTraversal(_ root: TreeNode?) -> [Int] {
  22.     var result = [Int]()
  23.     guard let root = root else { return result }
  24.     var stack = [root]
  25.     while !stack.isEmpty {
  26.         let current = stack.removeLast()
  27.         // 与前序相反，即中右左，最后结果还需反转才是后序
  28.         if let node = current.left { // 左
  29.             stack.append(node)
  30.         }
  31.         if let node = current.right { // 右
  32.             stack.append(node)
  33.         }
  34.         result.append(current.val) // 中
  35.     }
  36.     return result.reversed()
  37. }
  39. // 中序遍历迭代法
  40. func inorderTraversal(_ root: TreeNode?) -> [Int] {
  41.     var result = [Int]()
  42.     var stack = [TreeNode]()
  43.     var current: TreeNode! = root
  44.     while current != nil || !stack.isEmpty {
  45.         if current != nil { // 先访问到最左叶子
  46.             stack.append(current)
  47.             current = current.left // 左
  48.         } else {
  49.             current = stack.removeLast()
  50.             result.append(current.val) // 中
  51.             current = current.right // 右
  52.         }
  53.     }
  54.     return result
  55. }

二叉树的迭代遍历 - 图5