Leetcode刷题100天—144. 二叉树的前序遍历(二叉树)—day07

青旅半醒 2022-09-09 12:56 116阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![image-20210901115617356][]

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

**示例 1：**

![img][]

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

**示例 2：**

输入：root = []
    输出：[]

**示例 3：**

输入：root = [1]
    输出：[1]

**示例 4：**

![img][img 1]

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

**示例 5：**

![img][img 2]

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

**提示：**

*  树中节点数目在范围 \[0, 100\] 内
 *  **-100 <= Node.val <= 100**

**进阶**：递归算法很简单，你可以通过迭代算法完成吗？

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package 二叉树;
    
    import java.util.List;
    import java.nio.channels.NonWritableChannelException;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.Queue;
    
    /* * 2 * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ */
    public class _144_二叉树的前序遍历 { 
    // 递归，前序遍历
    // public List<Integer> preorderTraversal(TreeNode root) { 
    // 创建一个列表
    // List<Integer> res = new ArrayList<Integer>();
    // 将链表和列表放入到函数中
    // preorder(root, res);
    // 返回遍历后的结果
    // return res;
    // }
    //
    // public void preorder(TreeNode root, List<Integer> res) { 
    // 如果链表为空就直接返回结果
    // if (root == null) { 
    // return;
    // }
    // 将链表中的头节点值存入到列表中
    // res.add(root.val);
    // 在递归其左子树
    // preorder(root.left, res);
    // 在递归其右子树
    // preorder(root.right, res);
    // }
        
        
    // 迭代
    // public List<Integer> preorderTraversal(TreeNode root) { 
    // 设置列表
    // List<Integer> res = new ArrayList<Integer>();
    // 如果链表为空就直接返回
    // if (root == null) { 
    // return res;
    // }
     
    //设置栈
    // Deque<TreeNode> stack = new LinkedList<TreeNode>();
     指定根节点
    // TreeNode node = root;
     如果栈不为空或者node不为null就一直循环
    // while (!stack.isEmpty() || node != null) { 
     先循环左节点
    // while (node != null) { 
     获取节点值
    // res.add(node.val);
     将节点入栈
    // stack.push(node);
     指定下一个左节点
    // node = node.left;
    // }
     左节点循环完毕就到右节点
    // node = stack.pop();
    // node = node.right;
    // }
    // return res;
    // }
    
    // }
        
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210901115617356]: /images/20220829/06d7d32c58e0417a8868edc873c5d0dc.png
[img]: /images/20220829/6528528841374c719a643e544646ee7c.png
[img 1]: /images/20220829/8f8423bd30b64a70982b66982298ac91.png
[img 2]: /images/20220829/2dccf30f90654cefaf6b1c7c90224522.png