【算法刷题1】二叉树的前序遍历

解题思路

什么是二叉树的前序遍历？简单来说就是“根左右”，展开来说就是对于一颗二叉树优先访问其根节点，然后访问它的左子树，等左子树全部访问完了再访问其右子树，而对于子树也按照之前的访问方式，直到到达叶子节点。

从上述前序遍历的解释中我们不难发现，它存在递归的子问题：每次访问一个节点之后，它的左子树是一个要前序遍历的子问题，它的右子树同样是一个要前序遍历的子问题。

那我们可以用递归处理：

终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。

返回值：每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。

本级任务：每个子问题优先访问这棵子树的根节点，然后递归进入左子树和右子树。

因此处理的时候，过程就是：

step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。

step 2：从根节点开始进入递归，遇到空节点就返回，否则将该节点值加入数组。

step 3：依次进入左右子树进行递归。

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 {
            List<Integer> list = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = preOrder(root);
        int[] res = new int[list.size()];
         for(int i = 0;i<list.size();i++){
             res[i]=list.get(i);
         }
        return res;
      
    }
    List<Integer> preOrder(TreeNode node   ){
        if(node == null){
            return list;
        }
        list.add(node.val);
        preOrder(node.left);
        preOrder(node.right);
        return list;
    }
    
}