leetcode.94.binary tree inorder traversal 题解

原题地址

题目描述：Given a binary tree, return the inorder traversal of its nodes’ values.

简单来说就是一个二叉树的中序遍历。题目下面有Note，要求不要采用递归的解法。这里递归的解法是最容易理解的，但是一方面是慢，另一方面是要占用大量的空间，容易爆栈。这里采用循环的方式解；

构建一个指针p，如果p不为空，那么将p入栈，p指向p的左节点；

如果p为空，说明已经走到尽头了，那么将栈顶弹出，加入结果集，并且访问右节点；

代码：

public List<Integer> inorderTraversal(TreeNode root) {

    List<Integer> result = new ArrayList<>();

    Stack<TreeNode> stk = new Stack<>();

    TreeNode p = root;

    while (p != null || !stk.empty())
    {
        if(p != null)
        {
            stk.push(p);
            p = p.left;
        }
        else
        {
            p = stk.pop();
            result.add(p.val);
            p = p.right;
        }
    }

    return result;
}

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