题解 | #二叉树的前序遍历#

# 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
    #     """
    #     method_1: 根左右, 递归
    #     """
    #     rst = list()
    #     self.preorder(rst, root)
    #     return rst
    #     pass

    # def preorder(self, tre_:List[int], root: TreeNode):
    #     if root == None:
    #         return
        
    #     tre_.append(root.val)
    #     self.preorder(tre_, root.left)
    #     self.preorder(tre_, root.right)

    def preorderTraversal(self, root: TreeNode) -> List[int]:
        """
        method_2: 使用非递归的方法进行 二叉树前序遍历
        步骤： 
        step1: 判断树是否为空， 空树不遍历
        step2: 准备辅助栈， 首先记录根节点
        step3: 每次从栈中弹出一个元素，进行访问，然后验证该节点的左右子节点是否存在，存在就加入栈中，有限加入右节点
        """
        rsta = list()
        tmp_stack = list()

        if root == None:
            return []
        tmp_stack.append(root)

        while (tmp_stack):
            node = tmp_stack[-1]
            tmp_stack.pop()
            rsta.append(node.val)

            if node.right:
                tmp_stack.append(node.right)
            if node.left:
                tmp_stack.append(node.left)

        return rsta
        pass
		 二叉树的递归调用和非递归调用，应该熟读，会背