山西网站建设网站,社群营销活动策划方案,广告设计在哪里学,厦门建站服务文章目录理论基础二叉树的递归遍历前序遍历中序遍历后序遍历总结二叉树的层序遍历基础层序遍历二叉树的右视图理论基础
二叉树在结构上的两个常用类型#xff1a;
满二叉树完全二叉树
在功能应用上的比较常用的有#xff1a;
二叉搜索树#xff1a; 节点有权值、遵循”左…
文章目录理论基础二叉树的递归遍历前序遍历中序遍历后序遍历总结二叉树的层序遍历基础层序遍历二叉树的右视图理论基础
二叉树在结构上的两个常用类型
满二叉树完全二叉树
在功能应用上的比较常用的有
二叉搜索树 节点有权值、遵循”左小右大“平衡二叉搜索树AVL树 在二叉树的基础上增添了一个特性左右子树高度差不超过1
二叉树的存储方式 顺序存储使用数组在内存中连续分布 链式存储使用指针在内存中离散分布
二叉树的遍历方式
深度优先遍历可借助栈 前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法 广度优先遍历可借助队列 层序遍历迭代法
二叉树的定义
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;}
}二叉树的递归遍历
前序遍历 题目链接144. 二叉树的前序遍历 class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();preRead(root,result);return result;}public void preRead(TreeNode node,ListInteger list){if(node null) return;list.add(node.val);preRead(node.left,list);preRead(node.right,list);}
}中序遍历 题目链接94. 二叉树的中序遍历 class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();inRead(root,result);return result;}public void inRead(TreeNode node,ListInteger list){if(node null) return;inRead(node.left,list);list.add(node.val);inRead(node.right,list);}
}后序遍历 题目链接145. 二叉树的后序遍历 class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger result new ArrayList();postRead(root,result);return result;}public void postRead(TreeNode node,ListInteger list){if(node null) return;postRead(node.left,list);postRead(node.right,list);list.add(node.val);}
}总结
递归算法的三要素 确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 通过”参数传递“自顶向下传递信息通过”函数返回值“自底向上传递信息使用全局变量在各级函数间共享信息 确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。 确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
二叉树的层序遍历
基础层序遍历 题目链接102. 二叉树的层序遍历 层序遍历的逻辑
初始化一个队列首先将根节点放入队列中接下来循环往复如下操作 弹出队头元素将弹出元素的左右节点入队
这个题的要求在层序遍历的基础上增加了分层的逻辑解题逻辑如下
在层序遍历的基础上我们再初始化一个队列temp主队列命名为queue我们在queue中把当前层的元素弹出时并不立马将其左右元素入队queue而是将其添加到temp队列中当queue中所有元素弹完之后再将temp的元素全部添加到queue中这样就达成了queue中永远是二叉树中每层的所有元素
解题逻辑
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger result new ArrayList();DequeTreeNode queue new ArrayDeque();if(root null) return new ArrayListListInteger();queue.add(root);while(!queue.isEmpty()) {ListInteger part new ArrayList();DequeTreeNode temp new ArrayDeque();while (!queue.isEmpty()) {TreeNode node queue.poll();part.add(node.val);if(node.left ! null) temp.add(node.left);if(node.right ! null) temp.add(node.right);}result.add(part);while(!temp.isEmpty()) queue.add(temp.poll());}return result;}
}这个地方可以进一步改进
无需使用新的队列来临时存储一层的元素而是可以直接用一个变量界定一层的元素个数
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger result new LinkedList();DequeTreeNode queue new ArrayDeque();if(root null) return new ArrayListListInteger();queue.add(root);while(!queue.isEmpty()) {ListInteger part new LinkedList();int count queue.size();while (count 0) {TreeNode node queue.poll();part.add(node.val);if(node.left ! null) queue.add(node.left);if(node.right ! null) queue.add(node.right);count--;}result.add(part);}return result;}
}二叉树的右视图 题目链接199. 二叉树的右视图 解题逻辑
在前一题的基础上只将每一层的最后一个元素添加到结果集中就可以我们通过控制每层的长度变量当变量为1的时候才添加到结果集中
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger result new LinkedList();DequeTreeNode queue new ArrayDeque();if(root null) return new ArrayListInteger();queue.add(root);while(!queue.isEmpty()) {int count queue.size();while (count 0) {TreeNode node queue.poll();if(count 1) result.add(node.val);if(node.left ! null) queue.add(node.left);if(node.right ! null) queue.add(node.right);count--;}}return result;}
}
