嗨，我目前正在跟踪leetcode面试问题，我有这个解决方案，但我不能理解2件事
解决方案代码
public class Solution {
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;
}
}我添加了一个图像来引用解决方案[1]树中的值：https://i.stack.imgur.com/cqn9q.png
我不明白的是，while循环直到curr不为null或堆栈为空，但是当我们遍历左侧时，我们到达end，然后中断内部循环，pop stack=curr，add to list，然后等于curr to curr.right。
这就是我不明白的？在所附的图像中，最左边的节点值是4，没有子节点，这意味着它的右子节点将等于null，然后在结束解决方案时中断外部循环？
第二个问题，时间复杂度在解中是o（n），但它不是o（n）的平方，因为我们在一个循环中有一个循环？
感谢所有帮助，指出我不完全理解的地方
谢谢：）
1条答案
按热度按时间ax6ht2ek1#
理解这一点的有用方法是通过空运行代码。对于您提供的示例，跟踪如下所示。
初始电流=1
我们进入外部while循环。除非curr=null和堆栈都为空，否则我们不会退出它。
因为当我们到达最左边的叶节时，内部的。电流=4
内循环的下一次迭代导致curr为null，因此我们从中中断。此时，4从堆栈中弹出并插入到列表中。
curr转到4的右子级，该子级为空。
在外循环的下一次迭代中，curr为空。但是，由于堆栈仍然不是空的，所以我们仍然再次进入外循环。但是，由于curr为空，我们不进入内部循环。
我们从堆栈中弹出一个元素。这次是2。记住堆栈是后进先出（后进先出）
总的时间复杂度。两个嵌套循环不一定转化为二次复杂度。由于树中的每个节点只访问一次，所以总体复杂度仍然是o（n）。