当前位置：网站首页>二叉树终章
二叉树终章
2022-06-30 18:28:00 【牧..】
文章目录
二叉树终章
本文 还是 为 二叉树 的 练习题
来看第一个题
二叉树的最近公共祖先
附上代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
if(p == root || q == root) {
return root;
}
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
if(leftTree == null) {
return rightTree;
}
if(rightTree == null) {
return leftTree;
}
return root;
}
}
逻辑清晰些
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(p == root || q == root) return root;
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
if(leftTree != null && rightTree != null) {
return root;
}else if(leftTree != null) {
// 左树不为空，右数为空，
return leftTree;
}else {
// 右树不为空，左数为空
return rightTree;
}
}
}
完成了 以上 那么 我们接下来 在来一种方法
接下来就 与 求 链表 交点一个思路 没啥难度，那么 你能自己完成吗？？？
附上代码
class Solution {
public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
if(root == null || node == null) {
return false;
}
stack.push(root);
if(root == node) {
return true;
}
boolean flg = getPath(root.left,node,stack);
if(flg) {
return true;
}
flg = getPath(root.right,node,stack);
if(flg) {
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
getPath(root,p,stack1);
getPath(root,q,stack2);
int size1 = stack1.size();
int size2 = stack2.size();
if(size1 > size2) {
int ret = size1 - size2;
while(ret != 0) {
stack1.pop();
ret--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()) {
if(stack1.peek() == stack2.peek()) {
return stack1.peek();
}
stack1.pop();
stack2.pop();
}
}else {
int ret = size2 - size1;
while(ret != 0) {
stack2.pop();
ret--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()) {
if(stack1.peek() == stack2.peek()) {
return stack1.peek();
}
stack1.pop();
stack2.pop();
}
}
return null;
}
}
二叉搜索树与双向链表
接下来我们 来看这道题
附上代码
public class Solution {
TreeNode prev = null;
public void inorder(TreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
root.left = prev;
//这里如果 不加条件 root != null
// 就会出现 空指针异常
if(prev != null) {
prev.right = root;
}
prev = root;
inorder(root.right);
}
public TreeNode Convert(TreeNode root) {
// 创建完 了 双向链表那么就要 去找到 head 结点了
if(root == null){
return null;
}
inorder(root);
TreeNode head = root;
while(head.left != null) {
head = head.left;
}
return head;
}
}
从前序与中序遍历序列构造二叉树
附上代码
class Solution {
public int preIndex = 0;
public TreeNode createTreeBypandI(int[]preorder,int[]inorder,int inbegin,int inend) {
if(inbegin > inend) {
return null;
}
int ret = preorder[preIndex];
TreeNode root = new TreeNode(ret);
int rootIndex = findIndexOfI(inorder,inbegin,inend,ret);
if(rootIndex == -1) {
return null;
}
preIndex++;
root.left = createTreeBypandI(preorder,inorder,inbegin,rootIndex - 1);
root.right = createTreeBypandI(preorder,inorder,rootIndex+1,inend);
return root;
}
public int findIndexOfI(int[]inorder,int inbegin,int inend,int key) {
for(int i = inbegin;i<= inend;i++) {
if(inorder[i] == key) {
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null) {
return null;
}
return createTreeBypandI(preorder,inorder,0,inorder.length-1);
}
}
从中序与后序遍历序列构造二叉树
附上代码
class Solution {
public static int posIndex = 0;
public TreeNode c(int[]inorder,int[]postorder,int inbegin ,int inend) {
if(inbegin > inend) {
return null;
}
int ret = postorder[posIndex];
TreeNode root = new TreeNode(ret);
int rootIndex = findIndex(inorder,inbegin,inend,ret);
if(rootIndex == -1) {
return null;
}
posIndex--;
// 注意 后序遍历 是 左子树 --> 右子树 --> 根随
// 随意 这里需要先创建 右子树
root.right = c(inorder,postorder,rootIndex + 1,inend);
root.left = c(inorder,postorder,inbegin,rootIndex-1);
return root;
}
public int findIndex(int[] inorder,int inbegin, int inend,int key) {
for(int i = inbegin;i <= inend; i++){
if(inorder[i] == key) {
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder == null || postorder == null) {
return null;
}
// 初始化全局变量 preIndex
posIndex = postorder.length-1;
// c 创建 二叉树
return c(inorder,postorder,0,inorder.length - 1);
}
}
根据二叉树创建字符串
附上代码
class Solution {
public void trreeToString(TreeNode root,StringBuilder sb) {
if(root == null) {
return;
}
sb.append(root.val);
if(root.left != null) {
// 根据刚刚分析 只要 root.left != null 我们 就需要添加一个 （
sb.append("(");
trreeToString(root.left,sb);
sb.append(")");
}else {
// root.left == null
if(root.right == null) {
// 这里我们 刚刚分析，如果 root.right == null 说明此时 需要添加一个 ） ，
//我们可以放到递归返回的地方添加
return;
}else{
// root.right != null 这里我们就需要 添加一个()
sb.append("()");
}
}
//左树走完 来 右树
if(root.right != null) {
sb.append("(");
trreeToString(root.right,sb);
sb.append(")");
}else {
//root.right == null
// 此时 树为空直接 return 出去即可
return;
}
}
public String tree2str(TreeNode root) {
if(root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
trreeToString(root,sb);
return sb.toString();
}
}
二叉树的前序遍历非递归
附上代码
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
return list;
}
}
二叉树的中序遍历非递归
附上代码
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
// System.out.println(top.val+" ");
ret.add(top.val);
cur = top.right;
}
return ret;
}
}
二叉树的后序遍历非递归
附上代码
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) {
return list;
}
TreeNode cur = root;
TreeNode prev = null;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if(top.right == null || top.right == prev ) {
stack.pop();
list.add(top.val);
prev = top;
}else {
cur = top.right;
}
}
return list;
}
}
二叉树完结。
边栏推荐
- 为什么越来越多的人选择云渲染？
- mysql 递归
- Lenovo Yoga 27 2022, full upgrade of super configuration
- dtd建模
- 20220528 [talk about fake chips] those who are greedy for cheap often suffer heavy losses. Take stock of those fake memory cards and solid state drives
- mysql修改数据类型_MySQL修改字段类型[通俗易懂]
- Pyth-Solana链上联通现实的桥梁
- MQ优缺点(2022.5.2-5.8)
- Develop those things: how to add text watermarks to videos?
- 拓維信息使用 Rainbond 的雲原生落地實踐
猜你喜欢
Sqlserver SQL Server Management Studio and transact SQL create accounts and create read-only users to access the specified database
Entry node of link in linked list - linked list topic
美国服务器租用和托管服务哪个好?
Construction and practice of full stack code test coverage and use case discovery system
ArcGIS no plug-in load (no offset) day map
全技术栈、全场景、全角色云原生系列培训重磅首发，助力企业打造硬核云原生技术团队
Opencv data type code table dtype
Brief introduction of Feature Engineering in machine learning
法国A+ 法国VOC标签最高环保级别
Huaxing Securities: kitex practice under the original hybrid Cloud Architecture
随机推荐
基于STM32单片机的测温仪
20220528 [talk about fake chips] those who are greedy for cheap often suffer heavy losses. Take stock of those fake memory cards and solid state drives
Kalman滤波器--从高斯融合推导
详解kubernetes备份恢复利器 Velero | 深入了解Carina系列第三期
Video content production and consumption innovation
nats集群部署
How to use the low code platform of the Internet of things for service management?
Task04：集合运算-表的加减法和join等--天池龙珠计划SQL训练营学习笔记
MQ组成部分(2022.5.16-5.22)
Redis beginner to master 01
CTF流量分析常见题型(二)-USB流量
mysql 递归
20200525 Biotechnology - Sichuan Normal University self taught Biotechnology (undergraduate) examination plan txt
如何使用物联网低代码平台进行服务管理？
ROS advertisement data publishing tips - latch configuration
go之web框架 iris
商业智能BI与业务管理决策思维之四：业务成本分析
Development: how to install offline MySQL in Linux system?
拓维信息使用 Rainbond 的云原生落地实践
【UML】UML类图