题意整理

  • 给定一颗二叉树的根节点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)
  • 空间复杂度:递归栈的深度为log2nlog_2n,最坏情况下,递归栈深度为n,所以空间复杂度是O(n)O(n)

方法二(利用栈)

1.思路整理

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

图解展示:

alt

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)