二叉树迭代中序遍历While循环未正常终止问题求助
迭代式二叉树中序遍历的异常问题
我尝试实现一种不使用元组的迭代式二叉树中序遍历方法,但遇到了问题:栈列表会从[]变为[None],导致while循环多执行一次。
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: stack = [root] res = [] while stack: print("start",stack) curr = stack.pop() if curr.left: temp = curr.left curr.left = None if curr.right: stack.append(curr.right) curr.right = None stack.append(curr) stack.append(temp) else: res.append(curr.val) if curr.right: stack.append(curr.right) print("end",stack) return res
使用测试用例[1]运行时,打印输出为:
start [TreeNode{val: 1, left: None, right: None}] end [] start [None]
这意味着while循环结束时栈为[],循环本应终止,但栈突然变为[None]并多执行一次。我在每个append前加了打印但未找到原因,添加curr非空判断后问题解决,但仍不清楚原因,恳请解答!
更新:
将代码复制到另一平台的同一题目中可正常运行,这会不会是原题平台的bug?
内容的提问来源于stack exchange,提问作者Will
相关产品推荐
相关产品推荐

