144.二叉树的前序遍历

二叉树的遍历

有两种遍历树的策略：

深度优先搜索(DFS)

在这个策略中，我们采用深度作为优先级，以便从根开始一直到达某个确定的叶子，然后再返回根到达下一个分支。

深度优先搜索，又可以根据根节点，左子节点和右子节点的相对顺序被分为 前序遍历 ，中序遍历，后序遍历。
宽度优先搜索(BFS)

我们按照一层一层访问整棵树，高层次的节点将比低层次的节点先访问到。

如下图中，按照1 2 3 4 5比较不同的策略。

144. 二叉树的前序遍历

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

示例:

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

输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路一：

使用递归，先遍历头节点，再左，再右。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    ArrayList <Integer>list = new ArrayList<>();
    // 递归
    public List<Integer> preorderTraversalRecursive (TreeNode root) {

        if (root == null) return list;
        list.add(root.val);
        preorderTraversalRecursive(root.left);
        preorderTraversalRecursive(root.right);

        return list;
    }

思路二：

迭代，需要使用额外的栈空间存储结构。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


    public List<Integer> preorderTransversalRecursive1(TreeNode root){
        ArrayList <Integer>list = new ArrayList<>();
        if (root == null) return list;

        Stack <TreeNode>stack = new Stack();
        stack.push(root);

        while (!stack.isEmpty()){

            TreeNode node = stack.pop();
            list.add(node.val);

            if (node.right != null){
                stack.push(node.right);
            }

            if (node.left != null){
                stack.push(node.left);
            }
        }
        return list;
    }

时间复杂度： O(N)

空间复杂度： O(N)

以下是在稿纸上推导的二叉树前序迭代遍历流程

截屏2020-06-06上午12.20.21

Contents

二叉树的遍历

144. 二叉树的前序遍历

题解：

思路一：

思路二：