Leetcode 144 二叉树的前序遍历

二叉树的前序遍历

题目

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解答

• 思路：

  • 使用一个列表记录遍历过的值；
  • 每次先将当前节点的值加入结果集，然后递归遍历左右子树;

• 代码：

  def preorderTraversal(self, root):
      """
      :type root: TreeNode
      :rtype List[int]
  
      (knowledge)
  
      思路：
      1. 使用一个列表记录遍历过的值；
      2. 每次先将当前节点的值加入结果集，然后递归遍历左右子树;
      """
  
      def _preorderTraversal(root, result):
          if not root:
              return result
          result.append(root.val)
          _preorderTraversal(root.left, result)
          _preorderTraversal(root.right, result)
          return result
  
      result = []
      return _preorderTraversal(root, result)
  

测试验证

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        if self:
            return "{}->{}->{}".format(self.val, repr(self.left), repr(self.right))


class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype List[int]

        (knowledge)

        思路：
        1. 使用一个列表记录遍历过的值；
        2. 每次先将当前节点的值加入结果集，然后递归遍历左右子树;
        """

        def _preorderTraversal(root, result):
            if not root:
                return result
            result.append(root.val)
            _preorderTraversal(root.left, result)
            _preorderTraversal(root.right, result)
            return result

        result = []
        return _preorderTraversal(root, result)
    
    def preorderTraversal2(self, root):
        """
        :type root: TreeNode
        :rtype List[int]

        (knowledge)

        非递归解法
        思路：
        1. 使用一个列表记录遍历过的值；
        2. 每次访问当前值，并将右左子树入栈；
        """
        result, stack = [], [root]
        while stack:
            node = stack.pop()
            if not node:
                continue
            result.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
        return result