144. Binary Tree Preorder Traversal

naive级别递归三连其一：前序遍历。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    dfs(root, res);
    return res;
}

public void dfs(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);

    dfs(root.left, res);
    dfs(root.right, res);
}

递归的理解：先写出三个点的前序遍历，然后发现后面两个左右子树的if可以用dfs复用。

public void dfs(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);
        //  左边的坑：dfs(root.left, res);
        if (root.left == null) return;
        res.add(root.left.val);
        // 右边的坑：dfs(root.right, res);
        if (root.right == null) return;
        res.add(root.right.val);
}

栈：先push右边再push左边，保持左边元素永远在栈顶（第一个出栈），或者还有一种操作是当右边的入栈时先pop左边的点

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    LinkedList<TreeNode> s = new LinkedList<>();
    if (root != null) s.push(root);

    while (!s.isEmpty()) {
        TreeNode node = s.pop();
        res.add(node.val);
        if (node.right != null) s.push(node.right);
        if (node.left != null) s.push(node.left);
    }
    return res;
}