每日一道算法题--leetcode 144--二叉树的前序遍历--python

秒速五厘米 2022-01-20 12:05 197阅读 0赞

**【题目描述】**

**【代码思路】**

**【方法一 递归】** 使用递归的方式完成前序遍历，简单且常规，不多赘述，直接上代码

# Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def preorderTraversal(self, root):
            res=[]
            if not root:return res
            self.dfs(root,res)
            return res
            
        def dfs(self,root,res):
            if root:res.append(root.val)
            if root.left:self.dfs(root.left,res)
            if root.right:self.dfs(root.right,res)
    复制代码

【方法二 迭代利用栈】

python中的栈实际上就是用list数据结构来实现的，list的append相当于入栈，pop相当于出栈，符合栈这种数据结构后进先出的特点。 用栈来实现前序遍历就是，先让栈顶元素弹出，再将其右结点入栈，再将左结点入栈，在一个循环中，只要栈不为空，循环就继续.

为什么要右结点先入栈，左结点后入栈那？

这样才能保证左结点在栈中的位置一直在右结点之上，这样访问起来，左结点一定先于右结点，前序遍历就是先访问根结点，再访问左结点，再右结点，对于任意一颗子树都满足这样的条件。

上代码

# Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def preorderTraversal(self, root):
            res=[]
            stack=[]
            if not root:return res
            stack.append(root)
            while len(stack)!=0:
                top=stack.pop()
                res.append(top.val)
                if(top.right):stack.append(top.right)
                if(top.left):stack.append(top.left)
            return res
    复制代码