题目、144. 二叉树的前序遍历

原题链接：144. 二叉树的前序遍历

题目描述：

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

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

输入：root = [1,2]
输出：[1,2]
/

输入：root = [1,null,2]
输出：[1,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 list = new ArrayList();  //创建list集合，用于存放先序遍历的节点元素
        if(root == null) return list; //如果根节点为空，直接返回空的集合
        TreeNode node = root;         //获取根节点
        //创建堆结构
        Deque<TreeNode> stack = new LinkedList<>();
        //当堆不为空或二叉树节点不为空时
        while(!stack.isEmpty() || node != null){
            while(node != null){      //树节点不为空
                list.add(node.val);   //节点元素传入集合
                stack.push(node);     //同时节点如栈
                node = node.left;     //堆节点左孩子重复操作
                //当左子树所有的左孩子入栈，代表遍历完左子树的所有子节点
            }
            //堆顶节点出栈
            node = stack.pop();
            //循环遍历出栈节点的右孩子
            node = node.right;
        }
        return list;                  //返回存放先序遍历节点顺序的集合
    }
}

提交结果：