python - 二叉树中序遍历

Question

我写了这样一个解决方案给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]

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

Answer 1

您的解决方案存在的问题是:

• 如果没有左边，则打印节点并从子树返回而不向右走
• 如果你有左边，你追加它。这可能会导致无限循环(当您从左侧返回时，您将再次附加它)

修复您的解决方案:

• 如果没有左节点，打印节点并将右节点入栈
• 如果你有一个左边，将左边放在堆栈上并从 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