我的个人微信公众号：Microstrong

微信公众号ID：MicrostrongAI

微信公众号介绍：Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容，分享在学习过程中的读书笔记！期待您的关注，欢迎一起学习交流进步！

知乎主页：https://www.zhihu.com/people/MicrostrongAI/activities

Github：https://github.com/Microstrong0305

个人博客：https://blog.csdn.net/program_developer

144. 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）递归解法

from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:

    def preorderTraversal(self, root: TreeNode) -> List[int]:

        res = []

        def preorderTree(root, res):
            if root is None:
                return res

            res.append(root.val)

            if root.left != None:
                preorderTree(root.left, res)

            if root.right != None:
                preorderTree(root.right, res)

        preorderTree(root, res)

        return res


if __name__ == "__main__":
    root = TreeNode(1)
    level1_right = TreeNode(2)
    level2_left = TreeNode(3)

    root.right = level1_right
    level1_right.left = level2_left

    sol = Solution()
    print(sol.preorderTraversal(root))

（2）迭代解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        """
        迭代方法的需要使用栈，先把右孩子进栈，再左孩子进栈。
        步骤：
        1.根节点入栈。
        2.取出根节点，值加入结果，然后先加右孩子，后加左孩子。
        3.重复2
        :param root:
        :return:
        """
        if not root:
            return []

        res = []

        stack = []
        stack.append(root)

        while stack:
            node = stack.pop()
            if not node:
                continue
            res.append(node.val)
            stack.append(node.right)
            stack.append(node.left)

        return res