LeetCode.144 二叉树的前序遍历

1.题目

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

 

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

 

​

输入：root = [1,null,2,3]
输出：[1,2,3]

1.递归遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;//左孩子
 *     TreeNode right;//右孩子
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();//用集合来存放遍历得到的结果
        preorder(root,result);
        return result;

    }
    public void preorder(TreeNode root,List<Integer> result){
        if(root==null){//递归的出口
            return;
        }
        result.add(root.val);
        preorder(root.left,result);
        preorder(root.right,result);
    }
}

2.迭代遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null){//注意这个特殊条件！
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();//通过栈来遍历
        stack.push(root);//首先头结点是先放进去，然后再拿出来的，比较特殊
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();//这里就是拿出栈顶的元素
            result.add(node.val);//把这个结点的值val添加到集合里面去
            if(node.right!=null){//先把右孩子添加到栈里面
                stack.push(node.right);
            }
            if(node.left!=null){//再把左孩子添加到栈里面
                stack.push(node.left);
            }
        }
      return result;
    }
}