使用栈来模拟递归过程实现二叉树的遍历

二叉树的定义代码

          public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}

遍历代码

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while(stack.size()>0 || root!=null){if(root!=null){stack.add(root);root = root.left;}else{TreeNode t = stack.pop();res.add(t.val);root = t.right;}}return res;}

递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。

首先传入一个有值的二叉树节点，开始执行循环，如果当前节点非空，则将当前整个节点压入栈中，注意是整个节点而不是当前节点的val。然后用该节点的左节点，替换传入的节点，如此循环，一直到节点为null，则表示到了树的最底端，这时候就可以把原先压入到栈里的元素逐个取出，然后将节点的值添加到结果集中，然后转向右边，重复上述过程，最后输出的结果集就是中序遍历的结果