问答

当前位置

67. Binary Tree Inorder Traversal

  • Ta: 白岩

在第一个九章给出的解法里面,我不太明白第30-34行代码的操作是什么目的?因为我的理解是stack.peek().right == node判断的是当前在stack最顶端的节点的左节点是否等于它的右节点,这是不可能的事情。所以为什么需要这段代码而不直接在第27行stack.pop()呢?

https://www.jiuzhang.com/solution/binary-tree-inorder-traversal/

以下是按照这样的修改我写的AC答案:

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        while (!stack.empty()) {
            TreeNode temp = stack.pop();
            answer.add(temp.val);

            temp = temp.right;
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
        }

        return answer;
    }

1 个回复

2019-09-09 carry

你的这份答案其实Java第二份答案是类似的。然后第一份答案的stack.peek().right == node首先要看它的思路,它第27到第29行,每次是先获取stack.peek(),然后就add到res里了,没有给它stack.pop()了,所以在第30行到34行每次判断一下当前栈顶元素的右孩子是不是刚刚pop()的节点,如果是,那么就把这个也pop()了,因为它在27到29行那个时候已经add到res里了。整体思路就是,根进栈,左孩子进栈,左孩子出栈被add到res里,根被add到res里,右孩子进栈,右孩子出栈被add到res里,然后判断根是不是已经add了,add了就出栈。(最后这一步就是答案代码第33行,34行的作用)。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1