Skip to content

144. Binary Tree Preorder Traversal

难度: 中等

刷题内容

原题连接

  • https://leetcode.com/problems/binary-tree-preorder-traversal

内容描述

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?

解题方案

思路 1

Recursive递归,瞬秒

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        res.append(root.val)
        if root.left: 
            res.extend(self.preorderTraversal(root.left))
        if root.right:
            res.extend(self.preorderTraversal(root.right))
        return res

思路 2

或者我们可以先写一下先序遍历的函数,然后一个一个贴上去

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        res = []
        self.preorder(root,res)
        return res


    def preorder(self,root,res):
        if root == None:
            return
        res.append(root.val)
        self.preorder(root.left,res)
        self.preorder(root.right,res)

Iterative, 迭代

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:  
            return res  
        stack = []  
        stack.append(root)  

        while(len(stack) > 0):  
            node = stack.pop()  
            res.append(node.val)  
            if node.right:  
                stack.append(node.right)  
            if node.left:  
                stack.append(node.left)  
        return res


回到顶部