【LeetCode】144.二叉树的前序遍历

1.问题

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1

"图1"

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2

输入：root = []
输出：[]

示例 3

输入：root = [1]
输出：[1]

示例 4

"图2"

输入：root = [1,2]
输出：[1,2]

示例 5

"图3"

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

2.解题思路

2.1 递归

中序遍历的规则是 根-左-右，然后访问左子树、右子树时同样按照此规则遍历，非常容易通过递归实现，按照规则，代码非常容易写出来。定义 preorderTraversal(root) 为递归遍历函数方法，root 为根节点。伪代码：

root.val;
preorderTraversal(root.left);
preorderTraversal(root.right);

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log⁡n)，最坏情况下树呈现链状，为 O(n)。

2.2 迭代

显示利用栈结构，遍历二叉树。
引用LeetCode动态图解迭代过程：
1）访问根节点

"图4"

2）根节点入栈

"图5"

3）左子树根节点遍历、入栈

"图6"

4）左子树根节点出栈，遍历其左右子节点

"图7"

5）左根节点左子树不存在，遍历其右子树4

"图8"

6）左子树遍历完毕，遍历根节点右子树

"图9"

7）遍历右子树根节点，根节点出栈

"图10"

8）右子树根节点入栈

"图11"

9）右子树左节点遍历，入栈

"图12"

10）右子树左节点遍历完毕，该节点出栈

"图13"

11）遍历右子树右节点，右子树根节点出栈

"图14"

12）右子树右节点遍历，入栈

"图15"

13）右子树遍历完毕，出栈

"图16"

14）遍历完毕

"图17"

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

• 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log⁡n)，最坏情况下树呈现链状，为 O(n)。

3.代码

public class Solution {
    /**
     * 递归
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (null == root) {
            return new int[0];
        }
        List<Integer> list = new ArrayList();
        preorderTraversal2(list, root);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
 
 	//递归方法
    public void preorderTraversal2 (List<Integer> list, TreeNode root) {
        if (null == root) {
            return;
        }
        list.add(root.val);
        preorderTraversal2(list, root.left);
        preorderTraversal2(list, root.right);
    }
	
	//迭代，栈思想
	public List<Integer> preorderTraversal(TreeNode root) {
	        List<Integer> res = new ArrayList<>();
	        if (null == root) {
	            return res;
	        }
	        Stack<TreeNode> stack = new Stack<>();
	        stack.add(root);
	        TreeNode p;
	        while (!stack.isEmpty()) {
	            p = stack.pop();
	            res.add(p.val);
	            //先把右节点入栈
	            if (null != p.right) {
	                stack.add(p.right);
	            }
	            if (null != p.left) {
	                stack.add(p.left);
	            }
	        }
	        return res;
	    }
}