BM23 二叉树的前序遍历

解题思路：二叉树的前序遍历为根左右，很明显要用递归，先保存根节点的值，然后继续保存左孩子的值，然后才是右孩子的值，整个下来需要遍历整个二叉树，然后将保存的值list转成数组返回即可，时间复杂度O(n)，空间复杂度O(n)

import java.util.*;



public class Solution {
    

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        ArrayList list = new ArrayList<>();
        addToList(root, list);
        int size = list.size();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = list.get(i);
        }
        return array;
    }

    private void addToList(TreeNode root, ArrayList list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        addToList(root.left, list);
        addToList(root.right, list);
    }
}

也可以用java8的stream流来将list转数组返回

import java.util.*;



public class Solution {
    

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        ArrayList list = new ArrayList<>();
        addToList(root, list);
        int[] array = list.stream().mapToInt(x->x).toArray();
        return array;
    }

    private void addToList(TreeNode root, ArrayList list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        addToList(root.left, list);
        addToList(root.right, list);
    }
}

扩展：也可以使用非递归的方式来实现

import java.util.*;



public class Solution {
    

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (root == null) {
            return new int[0];
        }
        ArrayList list = new ArrayList<>();
        Stack 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);
            }
        }
        int[] array = list.stream().mapToInt(x->x).toArray();
        return array;
    }

}