BM23 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

递归最好理解：

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (root == null){
            return new int[0];
        }
        
        List<Integer> result = new ArrayList<Integer>();
        find(result, root);
        
        int[] array = new int[result.size()];
        for (int i = 0 ; i < result.size(); i++){
            array[i] = result.get(i);
        }
        return array;
    }
    
    private void find(List<Integer> result, TreeNode node){
        if (node == null){
            return;
        }
        
        result.add(node.val);
        find(result, node.left);
        find(result, node.right);
    }

 

迭代版：其实也是模拟了递归的流程，按根、左、右的顺序依次添加。

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (root == null){
            return new int[0];
        }
        
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        // 根节点入栈
        stack.push(root);
        while (!stack.empty()){
            TreeNode current = stack.pop();
            // 先根节点
            result.add(current.val);
            // 先入，后出
            if (current.right != null){
                stack.push(current.right);
            }
            // 后入，先出
            if (current.left != null){
                stack.push(current.left);
            }
        }
        
        int[] array = new int[result.size()];
        for (int i = 0 ; i < result.size(); i++){
            array[i] = result.get(i);
        }
        return array;
    }