144. 二叉树的前序遍历

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

解法一：递归

# 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 = []
        self.travel(root, res)
        return res

    def travel(self, root, res):  #辅助函数，注意要将结果集作为参数传入，才能在递归中修改结果集
        if root:
            res.append(root.val)
            self.travel(root.left, res)                   
            self.travel(root.right, res)

解法二：用栈

依照前序的递归遍历，先访问根，然后递归左子，再递归右子

与非递归中序的不同仅在于访问并记录节点值的时机

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        p = root	#工作节点
        s = []	#栈
        while p or s:
            while p:
                res.append(p.val)
                s.append(p)
                p = p.left
            p = s.pop()
            p = p.right
        return res

js

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  const res = []
  const stack = []
  let p = root
  while (p || stack.length > 0) {
    while (p) {
      stack.push(p)
      res.push(p.val)
      p = p.left
    }
    p = stack.pop()
    p = p.right
  }
  return res
};