94. Binary Tree Inorder Traversal

yesr

发布于 2020-05-04 14:09:27

28700

代码可运行

文章被收录于专栏：leetcode_solutions

运行总次数：0

代码可运行

【思路分析】

二叉树中序遍历的实现通常有两种方法：递归和迭代。

递归思路很简单，所以这里我只说迭代版本的思路。

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按照相同的规则访问其右子树。因此处理过程如下：

对任一结点p 1.若其左孩子不为空，则将p入栈并将p的左孩子置为当前的p，然后对当前结点p再进行相同的处理； 2.若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将栈顶结点的右孩子置为当前的p 3.直到p为null且栈为空则结束遍历

【代码实现】

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}