题目描述

给定一个二叉树，返回它的前序 遍历。

示例：

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

递归求解思路

1.经典递归，根->左->右递归即可。

Java代码实现

    List<Integer> res = new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root != null){
            res.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return res;
    }

迭代法求解思路

  1. 借助栈来处理节点的先后顺序即可。

Java代码实现

    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();

        if(root != null)
            stack.push(root);

        while(!stack.isEmpty()){
            root = stack.pop();

            res.add(root.val);

            if(root.right != null){
                stack.push(root.right);
            }

            if(root.left != null){
                stack.push(root.left);
            }
        }

        return res;
    }