题解 | #二叉树的前序遍历#

题意整理

• 给定一颗二叉树的根节点root。
• 求该二叉树的前序遍历。

方法一（递归）

1.思路整理

先序遍历的顺序是根、左、右。如果直接按照递归的思路进行遍历，只需在对应的位置将当前节点加入到序列即可。

2.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    List<Integer> list=new ArrayList<>();
    public int[] preorderTraversal (TreeNode root) {
        dfs(root);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    private void dfs(TreeNode root){
        if(root==null) return;
        //加入到序列
        list.add(root.val);
        //往左子树方向遍历
        dfs(root.left);
        //往右子树方向遍历
        dfs(root.right);
       
    }
}

3.复杂度分析

• 时间复杂度：需要遍历树中所有节点，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：递归栈的深度为$lo{g}_{2}nlog\_2n$，最坏情况下，递归栈深度为n，所以空间复杂度是$O(n)O(n)$。

方法二（利用栈）

1.思路整理

将根节点作为起点节点，如果当前节点不为空，不断将它以及它的左子节点入栈。入栈之前就将节点加入到pre序列，所以遵循根、左的顺序。如果节点为空的时候，说明是最后一个左子节点，此时需要往右子树方向遍历。

图解展示：

2.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    List<Integer> pre=new ArrayList<>();
    public int[] preorderTraversal (TreeNode root) {
        dfs(root);
        return pre.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    private void dfs(TreeNode root){
        if(root==null) return;
        TreeNode node=root;
        //新建栈
        LinkedList<TreeNode> s=new LinkedList<>();
        while(!s.isEmpty()||node!=null){
            //如果当前节点不为空，不断将它以及它的左子节点入栈
            if(node!=null){
                s.push(node);
                //直接将节点加入到pre中，顺序是根、左
                pre.add(node.val);
                node=node.left;
            }
            else{
                node=s.pop();
                //往右子树方向遍历
                node=node.right;
            }
        }
       
    }
}

3.复杂度分析

• 时间复杂度：需要遍历树中所有节点，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：栈的深度不超过n，所以空间复杂度是$O(n)O(n)$。