python - 二叉树有序遍历

我写了这样一个解决方案来Binary Tree Inorder Traversal - LeetCode

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: "TreeNode") -> "List[int]":
        stack, res = [root], []

        while stack:
            cur = stack[-1]
            cur = cur.left

            if cur == None:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
            else:
                stack.append(cur)
                cur = cur.left
        return res

但没有如预期的那样工作

Finished
Runtime: 48 ms
Your input  [1,null,2,3]
Output  [1]
Expected  [1,3,2]

我的解决方案有什么问题？

最佳答案

解决方案的问题是：
如果没有左边，则打印节点并从子树返回而不向右
如果你有一个左，你可以加上它这可能会导致无限循环（当您从左边返回时，您将再次附加它）
要修复解决方案：
如果没有左边的，打印节点并将右边的放在堆栈上
如果有左指针，请将左指针放在堆栈上，并从treenode中移除左指针，这样在返回时就不会再添加左指针。
另一种方法，如果你不能摧毁这棵树：
一直向左走，把所有的节点都放在堆栈上
从堆栈中移除节点时，打印该节点，向右，然后一直向左，将所有节点放在堆栈上。
班级解决方案：

def inorderTraversal(self, root: "TreeNode") -> "List[int]":
    stack, res = [root], []
    cur = stack[-1]
    while cur.left != None:
        stack.append(cur.left)
        cur = cur.left
    while stack:
        cur = stack.pop()
        res.append(cur.val)
        if cur.right != None:
            stack.append(cur.right)
            cur = cur.right
            while cur.left != None:
                stack.append(cur.left)
                cur = cur.left
    return res

关于python - 二叉树有序遍历，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56899309/