【LeetCode】144. 二叉树的前序遍历
2024-10-10 09:29:01
144. 二叉树的前序遍历
知识点：二叉树；递归；Morris遍历
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例
输入：root = [1,null,2,3]
输出：[1,2,3]
输入：root = []
输出：[]
输入：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 {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return list;
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
时间复杂度；0(N),每个节点恰好被遍历一次；
空间复杂度；O(N),递归过程中栈的开销；
解法二:迭代法
入栈一定是先右后左，这样出来才能使先左后右；
压入根节点；
1.弹出就打印；
2.如有右孩子，压入右；
3.如有左孩子，压入左；
/**
* 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) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if(root != null) stack.push(root);
while(!stack.isEmpty()){
TreeNode top = stack.pop();
list.add(top.val);
if(top.right != null) stack.push(top.right);
if(top.left != null) stack.push(top.left);
}
return list;
}
}
解法三：Morris遍历
构建从下到上的连接，一条路能够走遍所有节点；
/**
* 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 {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return list;
TreeNode cur = root;
TreeNode mostRightNode = null;
while(cur != null){
mostRightNode = cur.left;
if(mostRightNode != null){
//有左子树；
while(mostRightNode.right != null && mostRightNode.right != cur){
mostRightNode = mostRightNode.right; //找到左子树的最右节点；
}
if(mostRightNode.right == null){
mostRightNode.right = cur; //构建向上的连接；
list.add(cur.val);
cur = cur.left;
continue;
}else{
//第二次到节点，断开连接
mostRightNode.right = null;
cur = cur.right;
}
}else{
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
体会
二叉树的遍历是二叉树的最基础的，不仅要掌握递归写法，迭代法和morris遍历也需要掌握，更多详细可参考这篇总结二叉树
相关题目
相关链接
最新文章
- maven权威指南学习笔记（五）—— POM
- 在Visual Studio中设置多核并行编译
- python：爬虫
- C++混合编程之idlcpp教程Lua篇(8)
- SpringMVC学习系列（8） 之 国际化
- iOS - CABasicAnimation
- Android 毛玻璃效果
- maven 几个插件的使用
- spring AutowireCapableBeanFactory 自动注入
- Bubble Sort
- EasyUI datagrid数据表格的函数getData返回来的是什么
- OVERLAY代码重入
- UBUNTU系统常用基本命令
- 引擎介绍 - REngine
- Loadrunner 在controller中运行socket脚本时报错：Abnormal termination, caused by mdrv process termination 的原因和解决方法
- Xmpp学习之Android-smack入门指导
- pig里面没有if：不能判断一个条件后决定一个执行步骤
- sql 存储过程学习
- ORM的增删查
- android dm-verity 功能【转】