本文共 1012 字，大约阅读时间需要 3 分钟。

链接：

大意：

使用迭代的方法中序遍历二叉树。

思路：

使用一个栈（我使用的是顺序栈）stack存储已经遍历的树节点，并且当前遍历节点为栈顶元素的左孩子。若当前遍历节点为null，则将stack的栈顶元素值加入到遍历列表res中，弹出栈顶元素（top--），并使当前遍历节点为弹出节点的右孩子。

详情见代码。

代码：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    private final int SIZE = 100;    public List
   
     inorderTraversal(TreeNode root) {        List
    
      res = new ArrayList<>();        if (root == null)            return res;        TreeNode[] stack = new TreeNode[SIZE];        int top = -1; // 指向栈顶元素        // 当root为null且stack为空时跳出循环        while (root != null || top != -1) {            if (root != null) {                stack[++top] = root;                root = root.left;                } else { // root == null                res.add(stack[top].val);                root = stack[top--].right;            }        }        return res;    }}
    
   

结果：

结论：

使用迭代的方式对二叉树进行中序遍历。在迭代方式里，使用数据结构栈来代替递归方式中的一个个递归。 

转载地址：http://xtesi.baihongyu.com/