LeetCode：144.前序遍历

跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！
代码随想录

LeetCode：144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：

示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：

示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]

前序遍历递归法

• 确定入参，返回值
• 确定终止条件
• 确定单层递归逻辑

	public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        treversal(root, res);
        return res;
    }

    private void treversal(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
        res.add(root.val);
        treversal(root.left, res);
        treversal(root.right, res);
    }

前序遍历迭代法（非递归法）
通过栈来实现非递归遍历，因为是放入栈，所以需要先放right然后再放left，，先进后出；注意判空

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                res.add(node.val);
            }else{
                continue;
            }
            stack.push(node.right);
            stack.push(node.left);
        }
        return  res;
    }

也可以这样，只是判空逻辑不同

	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);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }