题解 | 二叉树的前序遍历

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型一维数组
#
class Solution:
    # 法一：递归法
    # def preorder (self,root:TreeNode,res:List[int]):
    #     if root==None:
    #         return
    #     else:
    #         #遍历顺序为先遍历根
    #         res.append(root.val)
    #         #再遍历左子树
    #         self.preorder(root.left,res)
    #         #最后遍历右子树
    #         self.preorder(root.right,res)

    # def preorderTraversal(self , root: TreeNode) -> List[int]:
    #     # write code here
    #     res=[]
    #     self.preorder(root,res)
    #     return res

    # 法二:利用栈的先进后出特点
    # 1.先将根放入栈中
    # 2.然后取出栈顶的值，并把其左右子树放入栈中(注意左子树要在右子树上方，所以先放右子树)
    # 3.反复循环，直到栈为空
    # 栈能保证左子树输出完，再输出右子树
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        if not root:#根为空节点直接返回答案为空
            return res
        stack.append(root)#将根节点放入栈中

        while stack:# 栈不空就反复运行
        #取栈顶的值放入res中，并把其左右子树重新放回栈中
            stack_top = stack[-1]#取出栈顶元素
            stack.pop()
            res.append(stack_top.val)
            #如果栈顶元素还有右子树，就入栈(先放右子树，才能保证栈顶为左子树)
            if stack_top.right:
                stack.append(stack_top.right)
            #如果栈顶元素还有左子树，就入栈
            if stack_top.left:
                stack.append(stack_top.left)

 

        #循环结束即为答案
        return res