114二叉树的前序遍历

# Definition for a binary tree node.
# 前序遍历的意思是先遍历根节点，随后遍历左子树	，最终是右子树
# 因而这道题可以用递归的方式 立即解出来。
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
from typing import List
class Solution:
    def preorderTraversal1(self, root: TreeNode) -> List[int]:
        self.res = []
        self.dfs(root)
        return self.res
    def dfs(self,root):
        if not root :return
        # 先遍历根节点
        self.res.append(root.val)
        # 随后遍历左子树
        self.dfs(root.left)
        # 随后是右子树
        self.dfs(root.right)
    # 下面是迭代更新的方式 	。
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root :return []
        # 将根节点压进栈
        stack,res = [root],[]
        # 当栈为空的情况下
，意味着全部的连接点都遍历了
        while stack:
            # 弹出来连接点
            node = stack.pop()
            # 分辨连接点是不是为空
            if node:
                # 将连接点放进目录
                res.append(node.val)
                # 将右连接点压进栈
                if node.right :
                    stack.append(node.right)
                # 将左连接点压进栈
                if node.left :
                    stack.append(node.left)
        return res

文章来源于网络，如有侵权请联系站长QQ61910465删除本文版权归qu快排seo www.sEoguRuBlog.com 所有,如有转发请注明来出,竞价开户托管,seo优化请联系QQ√61910465