python - 二叉树前序遍历

Question

我刚刚开始使用二叉树，我有一个任务，我必须对给定的二叉树“[1,null,2,3]”进行预序迭代遍历搜索。

我尝试使用我发现的新的二叉树模块，但它不起作用，我看到了一个 YouTube 视频，其中有人递归地做到了这一点，但我就是不明白。

#Input = [1,null, 2,3]
# 1
#  \
#   2
#  /
# 3
#Expected output = [1,2,3]


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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:

我只是一无所知，我写了一个算法，但我无法将它变成实际的功能代码。我也不明白 root: TreeNode 是如何工作的。它会将列表中的每个元素都转换为 TreeNode 对象吗？到目前为止，我最好的尝试就是这样，但它在很多方面显然都是错误的。

def preorderTraversal(self, root: TreeNode) -> List[int]:
    result = []
    for i in root:
        if i =! root[0] and root.left =! None:
            root.left = i
            if root.left =! null:
                root.left.left = i
            elif root.left == null:
                root.right.left = i
            elif root.left
            result.append(i)
        elif root.right == None:
            root.right = i

        else:
            continue

Answer 1

几点:

1. 函数 preorderTraversal 不应有 self 参数；它不是类的方法。
2. 我修改了 TreeNode 类，以便更方便地指定其子 TreeNode 对象。
3. 函数preorderTraversal将TreeNode对象作为参数。正如我在评论中提到的，您的语句 #Input = [1,null, 2,3] 很难理解。
4. 您需要保留未访问的 TreeNode 对象的后进先出 (LIFO) 堆栈，以实现迭代(而不是递归解决方案)。在下面的代码中，变量 nodes 就用于此目的。

代码:

from typing import List

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.x = val
        self.left = left
        self.right = right

n3 = TreeNode(3)
n2 = TreeNode(2, left=n3)
n1 = TreeNode(1, right=n2)

def preorderTraversal(root: TreeNode) -> List[int]:
    result = []
    nodes = []
    nodes.append(root) # initial node to visit
    while len(nodes): # any nodes left top visit?
        node = nodes.pop() # get topmost element, which is the next node to visit
        result.append(node.x) # "output" its value before children are visited
        if node.right is not None:
            # show this node must be visited
            nodes.append(node.right) # push first so it is popped after node.left
        if node.left is not None:
            # show this node must be visited
            nodes.append(node.left)
    return result

print(preorderTraversal(n1))

打印:

[1, 2, 3]

或更复杂的树:

        10 
      /   \ 
    8      2 
  /  \    / 
3     5  2 

n3 = TreeNode(3)
n5 = TreeNode(5)
n8 = TreeNode(8, left=n3, right=n5)
n2a = TreeNode(2)
n2b = TreeNode(2, left=n2a)
n10 = TreeNode(10, left=n8, right=n2b)

print(preorderTraversal(n10))

打印:

[10, 8, 3, 5, 2, 2]