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

解题心得： good job！真棒，前序遍历用递归的方法，是我自己做出来的！

二叉树使用栈stack来实现，跟之前一道题，就是获取链表最大的前k个值，有异曲同工之妙，都是，减少内存占用，先往栈转入有限的数据大小。

解题思路：

方法一：使用栈

stack.add(root). / while（!stack.isempty()） { top = stack.pop(); vist(top); stack.push(top.left); stack.push(top.right); }

方法二：递归

void func(TreeNode root) {
    if(root==null) return;
    vist(root);  //visit放的位置不一样，就是不一样的遍历顺序了
  	func(root.left);
  	func(root.right);
}

import java.util.*;

public class Solution {

    /**
     * 使用栈实现
     */
    public int[] preorderTraversal (TreeNode root) {
        if(root == null) {
            return new int[]{};
        }
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode top = stack.pop();
            res.add(top.val);
            // 这里是先存入右节点，再存左节点
            // 这样左节点，就可以先出了
            if(top.right!=null) {
                stack.push(top.right);
            }
            if(top.left!=null) {
                stack.push(top.left);
            }
        }
     
        int [] arr = new int[res.size()];
        for(int i=0; i<arr.length; i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }

    /**
     * 使用递归的实现- 我自己做的
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal2 (TreeNode root) {
        // write code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        preorderTreeNode(root, res);
        int[] arr = new int[res.size()];
        for(int i=0; i<res.size(); i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }

    public void preorderTreeNode(TreeNode root, ArrayList<Integer> res) {
        if(root == null) {
            return ;
        }
        res.add(root.val);
        preorderTreeNode(root.left, res);
        preorderTreeNode(root.right, res);
    }
}