94. Binary Tree Inorder Traversal

mingyangdai

于 2018-02-19 13:49:51 发布

阅读量134

点赞数

分类专栏：数据结构&算法文章标签： tree binary tree 二叉树 algorithm datastructure

本文链接：https://blog.csdn.net/daimingyang123/article/details/79336954

版权

数据结构&算法专栏收录该内容

94 篇文章

订阅专栏

Given a binary tree, return the inorder traversal of its nodes' values.

For example:

Given binary tree [1,null,2,3],

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

二叉树的非递归中序遍历

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

如果有左子节点就把左子节点放入stack 然后pop出来访问然后访问右节点