0. 前言

简单记录

1. 正文

1.1 方法一

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#

class Solution:
    def preorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        
        if not root: return []
        # 初始化stack
        stack = []
        # 输出列表
        res = [] 
        cur_node = root # 当前节点
        
        while(stack or cur_node):
            
            # 沿着当前节点的左分支一直走
            while cur_node:
                stack.append(cur_node)
                res.append(cur_node.val)
                cur_node = cur_node.left
                
            # 栈顶元素出栈
            node = stack.pop()
            cur_node = node.right
        return res

1.2 方法二

class Solution:
    def preorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        
        if not root: return []
        # 初始化stack
        stack = []
        # 输出列表
        res = [] 
        stack.append(root)
        
        while(stack):
            
            cur_node = stack.pop() # 栈顶元素出栈
            res.append(cur_node.val)
            
            # 当前元素右节点不为空，入栈
            if cur_node.right:
                stack.append(cur_node.right)
            # 当前元素左节点不为空，入栈
            if cur_node.left:
                stack.append(cur_node.left)
                
        return res