LeetCode94：二叉树的中序遍历（非递归实现）

LeetCode94：二叉树的中序遍历（非递归实现）

引用

CSDN

1.

https://m.blog.csdn.net/Zhangjiangyan711/article/details/145064152

题目描述

给定一个二叉树的根节点root，返回它的中序遍历。

解题思路

要实现二叉树的非递归中序遍历，必须要借助栈。整个操作可以看成是很多个只有左子树的单边树，从头结点开始一直向左下方走，将经过的结点依次入栈，直至没有左孩子了，弹出结点，同时指向当前结点的右孩子，那么右子树同样可以看成是以这个右孩子为头结点的多个单边树，重复上面的操作即可。

以下图的中序遍历为例，1、2、3结点依次入栈，结点3无左孩子，3弹出，指向右孩子4，4入栈，无左孩子，4弹出，4无右孩子，2弹出，2无右孩子，1弹出，指向右孩子5，5、6依次入栈，6无左孩子，6弹出，6无右孩子，5弹出，指向右孩子7，7无左孩子，7弹出，7无右孩子，此时栈空，无法继续弹出栈顶元素，遍历结束。

具体迭代步骤如下：

1. 空树无法遍历，直接返回空数组
2. 在非空二叉树中，首先将头结点压栈，再使root=root.left，将该结点的左孩子压栈，重复该操作（即：将二叉树的左边界依次压入栈中）
3. 判断当前结点是否为空（也就是步骤2最后一次执行压栈操作前指向的结点的左孩子是否存在），若为空，弹出栈顶元素（当前结点的父结点）并加入到数组中，同时让root=root.right，重复步骤2
4. 当所有结点全都出栈且当前结点也为空时，遍历不再继续，结束

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        else {
            Stack<TreeNode> stack = new Stack<>();
            while(!stack.isEmpty() || root != null) {
                if(root != null) {
                    stack.push(root);
                    root = root.left;
                }else {
                    root = stack.pop();
                    list.add(root.val);
                    root = root.right;
                }
            }
        }
        return list;
    }
}