有关102题

Question

老师，我主要纠结的点是node.left和node.right到底是左子树右子树还是node这个节点的左边节点，右边节点。因为之前算法中node.left和node.right一直是左子树，右子树。但是这题中，到第二层的9时，他没有左子树，又没有右子树。害理来说应该是进入到下一次循环了，但是之前队列已经将9这个节点弹出了，也就是说队列此时没有节点了。那么就该打印能出结果了。但是我清楚，我这么想肯定是错的，要不然题解也通过不了。我想问的是node.left，node.right难道还会根据情况而变，从左右子树变成左右节点吗？

Answer 1

liuyubobobo 2020-12-03 11:42:10

其实我没有特别理解你的问题。 node.left 和 node.right 不会变。但是你说的“从左右子树变成左右节点”，左右子树和左右节点是一回事儿。因为我们访问一棵树，靠的是这棵树的根节点。我们访问一整棵树，靠一个 root 就够了。

你可不可以在代码中标记一下，你认为代码执行到哪里，某个变量应该是什么？但实际是什么？你不能理解？

或者如果在哪里加一个打印输出，你认为应该打印输出出来什么？实际打印输出的结果是什么？你不能理解？

• 提问者 慕仰7036876 #1

  老师我不明白的是您的102题在Git中的答案，这里
  if(node.left != null)
                  queue.addLast(new Pair<TreeNode, Integer>(node.left, level + 1));
              if(node.right != null)
                  queue.addLast(new Pair<TreeNode, Integer>(node.right, level + 1));
  如果是前面的算法题，node.left,node.right应该是向下的左右子树。但是本题是在同一行进行遍历。最开始的节点是3，我的疑惑是，如果说node.left,node.right是向下的左右子树话。下一个节点应该是3的左子树9。而在队列中的节点变成了9之后，应该检查的是9的左子树和右子树，但是9是没有左子树和右子树的。而按照您的程序，9的下一个节点应该是20。用的应该是node.right，从9遍历到20。但是老师我不明白的一点就在这里，如果是按照之前向下遍历的左右子树，node.right是怎样从9遍历到20的呢？9没有左右子树，node.left和node.right应该都为空啊。如果9的node.right等于20的话，就说明node.right可以指向同行的右节点。那么面对一个节点既有右节点，又有右子树的情况下，使用了node.right后，他的下一个节点到底是右子树还是右节点呢？我的理解中右子树指的是下一行的，右节点指的是同行的。

• liuyubobobo 回复 提问者 慕仰7036876 #2

  "9的下一个节点应该是20。用的应该是node.right" 不对。不是 9 的 right 是 20；我们是顺次从 队列里取出元素，是我们在队列中放完 9 之后，又放了 20。所以先取出了 9，再取出了 20。我的建议是：你使用单步跟踪的方式，用这个小的测试用例运行一遍程序，观察一下，每一次我们往队列中放了谁？队列中是什么样子的？循环里每次又取出了谁。

• 提问者 慕仰7036876 回复 liuyubobobo #3

  好的，谢谢老师