二叉树递归套路：
左边界压入栈中：
这就导致了每次弹出栈的时候是左+根(右),右递推为(左+根(右))
二叉树的宽度:(先序遍历)
使用队列作为存储
尾部: 头部: 先放左边后放入右边的数:最后要求先进先出的打印即可.
public static void printWide(){
if(head == null){
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
Node cur = queue.poll();
System.out.println(cur.value);
if(cur.left = null ){
queue.add(cur.left);
}
if(cur.right = null){
queue.add(cur.right);
}
}
}
public static void printWide(){
if(head == null){
return;
}
Queue<Node> queue = new LinkedList<>();
Map<Node,Interger> map = new HashMap<>();
map.put(head,1);
queue.add(head);
//记录节点数
int curLevel = 1;
//记录层数
int curLevelNode = 0;
int max = Interger.MIN_VALUE;
while(!queue.isEmpty()){
Node cur = queue.poll();
if(curNodeLevel == curLevel ){
curLevelNode++;
}else{
max = Math.max(max,curLevel);
curLevel++;
curLevelNode = 1;
}
if(cur.left = null ){
queue.add(cur.left);
}
if(cur.right = null){
queue.add(cur.right);
}
}
}
遍历二叉搜索树(中序遍历即可)：
需要对于无序的二叉树进行遍历后使用递归的方式检查
public static int preValue = Interger.MINVALUE;
public static boolean checkBST(Node head){
if(head == null){
return true;
}
boolean isLeftBST = checkBST(head.left);
if(!isLeftBST){
return false;
}else if(head.value <= preValue){
return false;
}else{
preValue = head.value;
}
return checkBST(head.right);
}
完全二叉树:(只要有孩子节点不全就是false)
//不双全的节点却又不是叶节点
if(
leaf && !
(left !== null || right == null)
||
( left == null || right !== null)
)
//左右孩子不全
if(left != null){
queue.add();
}if(right != null){
queue.add();
}
if(left == null || right == null){
leaf = true;
}
平衡二叉树:(子树的左右树差不超过1):
子问题:
1.树的高度多少?
2.树平衡吗?
树的套路问题:(树型dp)
练吧!!!!!!!!!!
public static class ReturnData(){
public boolean isBST;
public int max;
public int min;
public ReturnData(boolean is ,int min ,int max){
isBST = is;
this.max = max;
this.min = min;
}
}
public static ReturnData process1(Node x){
if(x == null){
return null;
}
ReturnData left = process(x.left);
ReturnData right = process(x.right);
boolean isBST;
int min = x.value;
if(lfetData != null){
min = Math.min(max,left.mix);
man = Math.man(max,left.max);
}
//看左右就好了和上面一样的套路
boolean isBST = false;
if(
(leftData != null? (leftData.isBST && leftData <= x.value) : true)
&&
(rightData != null? (rightData.isBST && rightData <= x.value) : true
){
idBSt = true;
}
return new ReturnData(isBST,min,max);
}
1.解决满二叉树问题:(高度,节点个数)
public static boolean isFull(Node head){
if(head == null){
return true;
Info data = find(head);
return data.nodes = (1 << data.height - 1);
}
//建议包装类型
public static class Info{
public int height;
public int nodes;
public Info(int h,int n){
height = h;
nodes = n;
}
}
// 使用包装类型
public static Info find(NOde x){
if(x == null){
return new Info(0,0);
}
Info leftData = find(x.left);
Info rightData = find(x.right);
int height = Math.max(leftData.height+
rightData.height)+1;
int nodes = leftData.nodes +
rightData.nodes +1;
return new Info(height,nodes);
}
}
2.所有值的中位数(无法解开)
3.只适用于左右递归的条件
4.最低的公共祖先节点:
//初始化Node节点
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value = data;
}
}
//o1 和 o2 一定属于head 为头部的树
//返回 俩的最低公共祖先
public static Node lca(Node head,Node o1,Node o2){
HashMap<Node,Node> fatherMap = new HashMap<>();
fatherMap.put(head,head);
process(head, fatherMap);
HashSet<Node> set1 = new HashSet<>();
Node cur = o1;
}
while(cue=r != fatherMap.get(cur)){
set1.add(cur);
cur = fatherMap.get(cur);
}
public static void process(Node head , HashMap<Node,Node> fatherMap){
}
public static Node lowestAncestor(Node head, Node o1,Node o2){
if(head == null || head == o1 || head == o2){
return head;
} 0
//第二种情况最初的公告节点
Node left = lowestAncestor(head.left,o1,o2);
Node right = lowestAncestor(head.right,o1,o2);
//说明head就是LCA
if(left != null && right != null){
return head;
}
//左右两棵树,并不一定都有返回值
return left != null ? left : right;
}
1.01 和 02 分别是他们的最低公共祖先(LCA):
2.不是最低的公共祖先.
分为两类.
后继节点:(中序遍历的结果进行保存)
二叉树序列化和反序列化:
树的结构可以转化为字符串->序列化,反之反序列化
eg:
1_1--#--1--#--#--
//初始化Node节点
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value = value;
}
}
public static String serialByPre(Node head){
if(head == null){
return '_#';
}
String res = head.value+"_";
//左数序列化
res += serialByPre(head.left);
//右数
res += serialByPre(head.right);
return res;
}
//通过前驱来排序
public static Node reconByPreString(String preStr){
//统一封装输入
String[] values = perString.split("_");
//通过队列保存
Queue<String> queue = new LinkedList<>();
//便利加入队列
for(int i = 1;i != values.length ; i++){
queue.add(values[i]);
}
return reconPreOrder(queue);
}
//这是Node的返回值方法反序列化
public static Node reconPreOrder(Queue<String> queue){
String value = queue.poll();
if(value.equals("#")){
return null;
}
Node head = new Node(Interger.valueOf(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
微软:纸条折痕问题:
| 上方 | 3凹 | 2凹 | 3凸 | 1凹 | 3凹 | 2凸 | 3凸 | 下方 |
|---|
public static void printAllFolds(int N){
printProcess(1,N,true);
}
public static void printProcess(int i,int N,boolean down){
if(i < N){
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? "凹" : "凸");
printProcess(i + 1, N, false);
}
public static void main(String[] args){
//次数
int N = 3;
printAllFolds(N);
}
练习
代码随想录
结合拉不拉东所以决定从二叉树开始刷题。
二叉树部分
二叉树的种类
在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。
#满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
如图所示：
[图片上传失败...(image-14263b-1649069406096)]
这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。
#二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树 [图片上传失败...(image-fce14a-1649069406096)]
#平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
如图：
[图片上传失败...(image-f8860e-1649069406096)]
最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。
二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
tips:曾经在面试字节跳动的时候让我手写一个单链表结构并且做大数减法
这里真的要会自己写结构少用库
贴出来
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;
}
}
题目训练
总结全部的前中后
中序
/**
* 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 {
ArrayList<Integer> result = new ArrayList<Integer>();
public ArrayList<Integer> inorderTraversal(TreeNode root) {
//this的妙用
this.result = result;
inorder(root);
return result;
}
public void inorder(TreeNode root){
if(root == null){
return ;
}
inorder(root.left);
result.add(root.val);
inorder(root.right);
}
}
先序遍历二叉树
特性:可以求解深度
前序位置的代码执行是
自顶向下
104.二叉树的最大深度
/**
* 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 {
int res = 0;
int depth = 0;
public int maxDepth(TreeNode root) {
recur(root);
return res;
}
public void recur(TreeNode node){
if(node == null){
res = Math.max(res,depth);
return ;
}
//进入加一
depth+=1;
recur(node.left);
recur(node.right);
//离开减去1
depth-=1;
}
}
这个解法应该很好理解，但为什么需要在前序位置增加
depth，在后序位置减小depth？因为前面说了，前序位置是进入一个节点的时候，后序位置是离开一个节点的时候，
depth记录当前递归到的节点深度，所以要这样维护。
纯纯递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 利用定义，计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 整棵树的最大深度等于左右子树的最大深度取最大值，
// 然后再加上根节点自己
int res = Math.max(leftMax, rightMax) + 1;
return res;
}
}
后续遍历二叉树
特性:后序位置的代码执行是
自底向上这就方便我们处理一些
子树的问题
举具体的例子，现在给你一棵二叉树，我问你两个简单的问题：
1、如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
2、如何打印出每个节点的左右子树各有多少节点？
第一个问题可以这样写代码：
// 二叉树遍历函数
void traverse(TreeNode root, int level) {
if (root == null) {
return;
}
// 前序位置
printf("节点 %s 在第 %d 层", root, level);
traverse(root.left, level + 1);
traverse(root.right, level + 1);
}
// 这样调用
traverse(root, 1);
第二个问题可以这样写代码：
// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
if (root == null) {
return 0;
}
int leftCount = count(root.left);
int rightCount = count(root.right);
// 后序位置
printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
root, leftCount, rightCount);
return leftCount + rightCount + 1;
}
结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。
543.二叉树的直径
/**
* 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 {
//设置最大直径默认值为0
int maxdia = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxdia;
}
public int maxDepth(TreeNode root){
if(root == null){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
//可以不包括根节点
maxdia = Math.max(maxdia,left + right);
return Math.max(left,right) + 1;
}
}
补充算法:
刚刚做了一道类似的题
124. 二叉树中的最大路径和，
虽然是Hard但解法和本题一毛一样～～ 唯一的区别是：不是求边长，而是路径上节点的value之和，因为节点的value可能是负数，因此求左孩子右孩子的时候要int leftSum = Math.max(0, dfs(root.left));舍弃掉负数的结果。
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int leftSum = Math.max(0, dfs(root.left));
// 和上题唯一的区别在这里，如果左右孩子的结果是负数的话就舍弃。
int rightSum = Math.max(0, dfs(root.right));
max = Math.max(max, leftSum + rightSum + root.val);
return Math.max(leftSum, rightSum) + root.val;
}
}
>>>>>>>>>>再更新：哎码又碰到了一样的题>>>>>>>>>>>>>
/**
* 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 {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
recur(root);
return max;
}
//分解为子问题（保证当前节点root 加入的是否是最大的
public int recur(TreeNode root){
//终止条件
if(root == null){
return 0;
}
//开启递归
int left = Math.max(0,recur(root.left));
int right = Math.max(0,recur(root.right));
max = Math.max(max, left + right + root.val);
return Math.max(left,right) + root.val;
}
}
687. 最长同值路径
和本题又一毛一样，遍历所有节点，以每个节点为中心点求最长路径（左右子树的边长之和），更新全局max。唯一的区别是，求出了左孩子的边长leftSize后，如果左孩子和当前节点不同值的话，那要把leftSize重新赋值成0。
ARTS/A-20190925-最长同值路径.md at master · echofoo/ARTS · GitHub
超级详细的解析十分好用
官解详解。。。
class Solution {
int ans;
public int longestUnivaluePath(TreeNode root) {
ans = 0;
arrowLength(root);
return ans;
}
public int arrowLength(TreeNode node) {
if (node == null) return 0;
int left = arrowLength(node.left);
int right = arrowLength(node.right);
int arrowLeft = 0, arrowRight = 0;
if (node.left != null && node.left.val == node.val) {
arrowLeft = left + 1;
}
if (node.right != null && node.right.val == node.val) {
arrowRight = right + 1;
}
ans = Math.max(ans, arrowLeft + arrowRight);
return Math.max(arrowLeft, arrowRight);
}
}
1、首先，递归函数arrowLength(TreeNode node )返回的并不是以node为根的树（子树）中的最长路径长度，而是以node为根（不考虑父节点）且包含node本身所在的单侧“最长“同值路径的长度（单侧即题解里提到的“箭头”，即只考虑左或者右其中一个分支，将在第二点中详细说明）。
所以如果当前节点为叶子节点，或者该节点与其左右孩子节点的值都不相等时，调用函数arrowLength返回的都是0。
例如
2 <<
/ \
3 3 <<
\
3
这里的根节点2的调用arrowLength结果为0，因为该值与其左右子节点的值都不相等，即这个2本身所在的单侧最长同值路径只包含它自己，
没有边，所以为0。
对以第二层右边这个3为根节点的子树 3 ,对这个根3调用arrowLength()的结果应该是1。代表当前这个1所处的单侧最长同值路径包含1条边.
\
3
另外两个叶子节点3，返回值都是0。
上面这颗树，调用arrowLength返回的结果依次对应为
0 => 左右子树值与当前值都不相等
/ \
0 1 => arrowRight = 0 + 1
\
0 => 只考虑以其为根的子树中它所在的最长路径，不考虑父节点，所以也为0。
再来两个例子,左图为构造的子图，右图为对应每个节点arrowLength的返回值
2 1
\ \
2 0
\ \
1 => 2
\ \
1 1
\ \
1 0
2 2
\ \
2 1
\ \
2 => 0
\ \
1 1
\ \
1 0
2、其次，每个节点有一个单侧最长路径，和一个真正的(双侧)最长路径，单侧最长路径用来返回给上一个节点，也就是arrowLength 中的return的值，真正的最长路径是用来做比较 ，也就是 ans 的值。
举例来说
3
/
3 <<
/ \
3 3
\
3
第二层的节点3 ，单侧最长路径是2，双侧最长路径是3
单侧最长路径： 在左右分支中选长的那条 => Math.max(arrowLeft, arrowRight)
双侧最长路径： 左右分支之和 => arrowLeft + arrowRight
为什么要这样分呢？
因为在第二层的节点3为根的子树中，对于这个根节点3本身来说，它所在的最长同值路径：是从“其左节点->其本身->其右节点”形成的3个节点的路径，
所以所包含的边是2。
但它不能把这个2传给其父节点（即return给上一层递归的函数）。
因为其父节点在计算最长路径的时候，只能选择“其父节点->其本身->其左孩子”或者“其父节点->其本身->其左孩子”，不能将其两个孩子的路径都
包含在内，最能返回左右分支中较长的那一个。
所以在做迭代计算时，每个节点的返回值对应为
3 => max(arrowLeft = 2+1, arrowRight = 0)
/
2 = > max(arrowLeft = 0+1, arrowRight = 1+1)
/ \
0 1 = > max( arrowRight = 0 + 1 ,arrowLeft = 0 )
\
0
上层的节点是由其子节点返回值中的较大值+1得到的（父与子的值相同的情况下，值不相同则父为0）。
而每个节点真正用来比较的res,即arrowLeft + arrowRight 为：
3 => 3 + 0
/
3 => 1 + 2
/ \
0 1 => 0 + 1
\
0
3、最后比较出所有节点的res值中最大值，即为longestUnivaluePath的最终返回值。
总结：
递归函数arrowLength中做了两件事：
1、计算以当前节点为根、且经过当前节点的最长单侧路径的边数，该值用来返回给父节点。
2、对每一个节点计算以当前节点为根、且经过当前节点的最长路径（双侧）的边数，所有节点中的最大值即是要求的结果。
class Solution {
int max = 0;
public int longestUnivaluePath(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root.left == null && root.right == null) {
return 0;
}
int leftSize = root.left != null? dfs(root.left) + 1: 0;
int rightSize = root.right != null? dfs(root.right) + 1: 0;
if (leftSize > 0 && root.left.val != root.val) {
// 唯一的区别在这里，按照上题思路求出了左边边长后， 如果当前节点和左孩子节点不同值，就把边长重新赋值为0。
leftSize = 0;
}
if (rightSize > 0 && root.right.val != root.val) {
// 同上。
rightSize = 0;
}
max = Math.max(max, leftSize + rightSize);
return Math.max(leftSize, rightSize);
}
}
在这里使用一个测试用例
为什么 [1,null,1,1,1,1,1,1] 这个测试用例的答案是4而不是6？
/** * 1 * / \ * null 1 * / \ * 1 1 * / \ / * 1 1 1 */
层序遍历
按照层数进行操作迭代需要借助队列
见剑指offer 三联
二叉树题型主要是用来培养递归思维的，而层序遍历属于迭代遍历，也比较简单，这里就过一下代码框架吧：
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// 从上到下遍历二叉树的每一层
while (!q.isEmpty()) {
int sz = q.size();
// 从左到右遍历每一层的每个节点
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 将下一层节点放入队列
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
}
这里面 while 循环和 for 循环分管从上到下和从左到右的遍历：
[图片上传失败...(image-e4e0ef-1649069406096)]
前文 BFS 算法框架 就是从二叉树的层序遍历扩展出来的，常用于求无权图的最短路径问题。
当然这个框架还可以灵活修改，题目不需要记录层数（步数）时可以去掉上述框架中的 for 循环，比如前文 Dijkstra 算法 中计算加权图的最短路径问题，详细探讨了 BFS 算法的扩展。
两种模板DFS和BFS
// 102.二叉树的层序遍历
class Solution {
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
//checkFun01(root,0);
checkFun02(root);
return resList;
}
//DFS--递归方式
public void checkFun01(TreeNode node, Integer deep) {
if (node == null) return;
deep++;
if (resList.size() < deep) {
//当层级增加时，list的Item也增加，利用list的索引值进行层级界定
List<Integer> item = new ArrayList<Integer>();
resList.add(item);
}
resList.get(deep - 1).add(node.val);
checkFun01(node.left, deep);
checkFun01(node.right, deep);
}
//BFS--迭代方式--借助队列
public void checkFun02(TreeNode node) {
if (node == null) return;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while (!que.isEmpty()) {
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
}
}
例题由浅入深刷二叉树
层序遍历试题:
共十道
102.二叉树的层序遍历
模板不解释107.二叉树的层次遍历II
反转模板不解释199.二叉树的右视图
开启 根 -> 右 -> 左 的优秀递归策略637.二叉树的层平均值 计算平均值的话
`DFS`需要多个新变量在主方法中计算 `BFS`则用常数空间的变量在添加时进行计算429.N叉树的前序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度
2.二叉树的右视图思路
二叉树的右视图
一、BFS
利用广度优先搜索进行层次遍历，记录下每层的最后一个元素。
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == size - 1) { //将当前层的最后一个节点放入结果列表
res.add(node.val);
}
}
}
return res;
}
}
二、DFS
我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。
（与先序遍历 「根结点 -> 左子树 -> 右子树」 正好相反，先序遍历每层最先访问的是最左边的节点）
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0); // 从根节点开始访问，根节点深度是0
return res;
}
private void dfs(TreeNode root, int depth) {
if (root == null) {
return;
}
// 先访问 当前节点，再递归地访问 右子树 和 左子树。
if (depth == res.size()) { // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
res.add(root.val);
}
depth++;
dfs(root.right, depth);
dfs(root.left, depth);
}
}
4.二叉树的层平均值
这道题模板够多了
主要是
DFS如何取进行算平均值的计算方法
/**
* 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<Double> averages = new ArrayList<Double>();
public List<Double> averageOfLevels(TreeNode root) {
bfs(root);
return averages;
}
public void bfs(TreeNode root){
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
double sum = 0.0;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sum += node.val;
TreeNode left = node.left, right = node.right;
if (left != null) {
queue.offer(left);
}
if (right != null) {
queue.offer(right);
}
}
averages.add(sum / size);
}
}
}
// public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
// if (root == null) {
// return;
// }
// 重点看这里
// if (level < sums.size()) {
// sums.set(level, sums.get(level) + root.val);
// counts.set(level, counts.get(level) + 1);
// } else {
// sums.add(1.0 * root.val);
// counts.add(1);
// }
// dfs(root.left, level + 1, counts, sums);
// dfs(root.right, level + 1, counts, sums);
// }
5.N 叉树的层序遍历
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
public List<List<Integer>> levelOrder(Node root) {
// dfs(root,0);
BFS(root);
return result;
}
//递归写法
public void dfs(Node root, int depth){
if(root == null){
return ;
}
//代表迭代时，已经进入节点但是未添加到结果集合中
//和之前的模板不一样了
//原理是我们第一次进入的时候是0，size也是0
if(depth >= result.size()){
List<Integer> temp = new ArrayList<Integer>();
result.add(temp);
}
//根据索引来添加层对应的节点
result.get(depth).add(root.val);
//开启递归
for(Node node : root.children){
if(node != null){
dfs(node ,depth + 1);
}
}
}
//BFS广度优先
public void BFS(Node root){
if(root == null){
return ;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
// while(!queue.isEmpty()){
// List<Integer> list = new ArrayList<Integer>();
// int size = queue.size();
// for(int i = 0;i < size;i++){
// Node temp = queue.poll();
// list.add(temp.val);
// // queue.addAll(root.children);
// for(Node node : root.children){
// if(node != null){
// queue.offer(node);
// }
// }
// }
// result.add(list);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
level.add(node.val);
// queue.addAll(node.children);
//往下面遍历的话是队列里面的 弹出来的哪个节点
for(Node temp : node.children){
queue.add(temp);
}
}
result.add(level);
}
}
}
在每个树行中找最大值
使用了两种方法
/**
* 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> result = new LinkedList<Integer>();
public List<Integer> largestValues(TreeNode root) {
// //dfs
// dfs(root,0);
bfs(root);
return result;
}
public void dfs(TreeNode root,int depth){
if(root == null){
return ;
}
if(depth >= result.size()){
result.add(root.val);
}
//d代表可以从 在当前的层里面进行操作，例如计算和还有计算节点数量
else{
result.set(depth,Math.max(root.val,result.get(depth)));
}
dfs(root.left,depth + 1);
dfs(root.right,depth + 1);
}
public void bfs(TreeNode root){
if(root == null){
return ;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer>temp = new LinkedList<Integer>();
int size = queue.size();
for(int i = 0 ; i < size ; i++){
TreeNode level = queue.poll();
temp.add(level.val);
//二叉树的特性加入左右节点
//如果是N叉叉的需要遍历节点加入孩子节点
if( level.left != null){
queue.offer(level.left);
}
if(level.right != null){
queue.offer(level.right);
}
}
result.add(Collections.max(temp));
}
}
}
填充每个节点的下一个右侧节点指针
这里主要就是注意方法论了
完美二叉树是什么呢
其所有叶子节点都在同一层，每个父节点都有两个子节点。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
😒:分析:
让这个指针指向其下一个右侧节点
解读:
root.left.next ---> root.right从而链接起来
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
// bfs(root);
if(root == null){
return null;
}
recur(root.left,root.right);
return root;
}
//递归
public void recur(Node left,Node right){
if(left == null || right == null){
return ;
}
//核心是在说什么呢
//就是把左节点的next 与右边的节点连接起来
left.next = right;
//当这俩是一个父亲节点的时候
//这俩节点是兄弟的时候
recur(left.left,left.right);
recur(right.left,right.right);
//当这俩节点是孙子辈
//即这俩节点的父节点不同但需要链接时
recur(left.right,right.left);
}
// //dfs
//深度优先不在适合解释当前的题目
// public void dfs(Node root,int depth){
// if(root == null){
// return ;
// }
// if(depth >= )
// }
//bfs
public void bfs(Node root){
//出口
if(root == null){
return ;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
//按照层左-》右遍历
for(int i = 0 ; i < size ; i++){
//头节点出队
Node temp = queue.poll();
//操作节点
if(i < size - 1 ){
temp.next = queue.peek();
}
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
}
}
}
填充每个节点的下一个右侧节点指针 II
模板化的写法,需要在每层的时候把节点串联起来即可
需要我们加入哑巴节点
dummy
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
// bfs(root);
NodeType(root);
return root;
}
public void NodeType(Node root){
if (root == null)
return ;
//cur我们可以把它看做是每一层的链表
Node cur = root;
while (cur != null) {
//遍历当前层的时候，为了方便操作在下一
//层前面添加一个哑结点（注意这里是访问
//当前层的节点，然后把下一层的节点串起来）
Node dummy = new Node(0);
//pre表示访下一层节点的前一个节点
Node pre = dummy;
//然后开始遍历当前层的链表
while (cur != null) {
if (cur.left != null) {
//如果当前节点的左子节点不为空，就让pre节点
//的next指向他，也就是把它串起来
pre.next = cur.left;
//然后再更新pre
pre = pre.next;
}
//同理参照左子树
if (cur.right != null) {
pre.next = cur.right;
pre = pre.next;
}
//继续访问这一行的下一个节点
cur = cur.next;
}
//把下一层串联成一个链表之后，让他赋值给cur，
//后续继续循环，直到cur为空为止
cur = dummy.next;
}
}
public void bfs(Node root){
if(root == null){
return ;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
Node pre = null;
for(int i = 0 ; i < size ; i++ ){
Node temp = queue.poll();
//如果pre为空就表示node节点是这一行的第一个，
//没有前一个节点指向他，否则就让前一个节点指向他
if(pre != null){
pre.next = temp;
}
//往后走
pre = temp;
if (temp.left != null)
queue.add(temp.left);
if (temp.right != null)
queue.add(temp.right);
}
}
}
}
[图片上传失败...(image-757f40-1649069406096)]
二叉树的最小深度
分出来深度优先和广度优先两种解法
考虑的问题:
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。``说明：叶子节点是指没有子节点的节点。`
：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
/**
* 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 {
class QueueNode {
TreeNode node;
int depth;
public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public int minDepth(TreeNode root) {
//dfs
//bfs
return bfs(root);
}
public int bfs(TreeNode root){
if (root == null) {
return 0;
}
Queue<QueueNode> queue = new LinkedList<QueueNode>();
queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node;
int depth = nodeDepth.depth;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}
}
return 0;
}
public int dfs(TreeNode root){
if(root==null)
return 0;
if(root.left==null && root.right==null)
return 1;
if(root.left!=null && root.right!=null)
return Math.min(minDepth(root.left),minDepth(root.right))+1;
if(root.left!=null)
return minDepth(root.left)+1;
if(root.right!=null)
return minDepth(root.right)+1;
return 1;
}
}
对称二叉树
也不是这么说的
对称要做的就是看是否
左子树和右子树是否对称对称的话条件有
在我们遍历时,当递归走到结束,此时1.
root.left == null && root.right == null代表此时左右都匹配,即便没有也是堆成的2.不对称的有:
2.1左右不一样,一个到底了一个还有
递归的话我们需要的是 便利的顺序,便利的顺序我们考虑了左右子树的问题
所以我们采用
后续遍历的方式去遍历
递归三部曲
- 确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下：
bool compare(TreeNode left, TreeNode right)
- 确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
- 左节点为空，右节点不为空，不对称，return false
- 左不为空，右为空，不对称 return false
- 左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
- 左右都不为空，比较节点数值，不相同就return false
此时左右节点不为空，且数值也不相同的情况我们也处理了。
代码如下：
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left.val != right.val) return false; // 注意这里我没有使用else
注意上面最后一种情况，我没有使用else，而是elseif， 因为我们把以上情况都排除之后，剩下的就是 左右节点都不为空，且数值相同的情况。
- 确定单层递归的逻辑
此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
- 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
- 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
- 如果左右都对称就返回true ，有一侧不对称就返回false 。
代码如下：
bool outside = compare(left.left, right.right); // 左子树：左、 右子树：右
bool inside = compare(left.right, right.left); // 左子树：右、 右子树：左
bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理）
return isSame;
如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。
/**
* 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 boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return compare(root.left,root.right);
}
public boolean bfs(TreeNode left,TreeNode right){
//借助队列操作左右子树，按照对称的方式镜像判断
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//将里昂节点入队
queue.offer(left);queue.offer(right);
//从上到下遍历节点
while(!queue.isEmpty()){
TreeNode left1 = queue.poll();
TreeNode right1 = queue.poll();
if(left1 == null && right1 == null){
return true;
}else if(left1 == null || right1 == null){
return false;
}else if(left1.val != right1.val){
return false;
}
queue.offer(left1.left);
queue.offer(right1.right);
queue.offer(left1.right);
queue.offer(right1.left);
}
return true;
}
//为了最小化代价所以我们写函数的时间尽量和原来的参数一致
public boolean compare(TreeNode left,TreeNode right){
//开始分析左右节点的情况
//1.
//2.
//3.
if(left == null && right != null){
return false;
}else if(left != null && right == null){
return false;
}else if(left == null && right == null){
return true;
}
//此时来到了左右长得一样但是值判断的条件中
else if(left.val != right.val) return false;
//递归看啊看你这左右子树的对称吗
boolean outside = compare(left.left,right.right);
boolean inside = compare(left.right,right.left);
boolean isSame = outside&&inside;
return isSame;
}
}
完全二叉树
什么是完全二叉树？
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点。
大家要自己看完全二叉树的定义，很多同学对完全二叉树其实不是真正的懂了。
我来举一个典型的例子如题：
[图片上传失败...(image-7bd90b-1649069406096)]
相信不少同学最后一个二叉树是不是完全二叉树都中招了。
之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。
重点在
偏左的位置
完全二叉树的节点个数
考虑啊
1.如果是递归的化我们怎么做保证他是 可以找到节点数量的
`后序遍历`
结合我们之前做过的和节点一样的遍历过程可以发现
he和
层序遍历一样
/**
* 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 {
int count = 0;
public int countNodes(TreeNode root) {
// return recur(root);
return bfs(root);
}
public int bfs(TreeNode root){
if(root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
//c从上到下遍历的是‘
//操作的是队列所以每次判断都是队列弹出的当前节点的左右节点
while(!queue.isEmpty()){q
int size = queue.size();
for(int i = 0 ; i < size ; i++){
TreeNode temp = queue.poll();
count ++ ;
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
}
return count;
}
public int recur(TreeNode root){
if(root == null){
return 0;
}
int leftCount = recur(root.left);
int rightCount = recur(root.right);
return 1+leftCount+rightCount;
}
}
平衡二叉树
是否平衡主要就是需要看待我们
左子树和右子树之间的距离比较深度 采用前序遍历
永远记住一句话
进入左节点 depth +1 右节点出去 depth - 1
二叉树的所有路径
条件为到达底端节点
/**
* 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<String> result = new LinkedList<String>();
public List<String> binaryTreePaths(TreeNode root) {
recur(root,"");
return result;
}
//需要构造函数 来进行结果的操作
//还需要一个用来添加 临时路径的变量String path
public void recur(TreeNode root,String path){
// if(root != null){
// StringBuffer temp = new StringBuffer(path);
// temp.append(Integer.toString(root.val));
// //当左右子节点为空代表已经走完了
// //这个时候需要 添加到结果和中返回
// if(root.left == null && root.right == null){
// result.add(temp.toString());
// } else{
// //此时的路径还不完全
// temp.append("->");
// recur(root.left,path);
// recur(root.right,path);
// }
// }
if (root != null) {
StringBuffer pathSB = new StringBuffer(path);
pathSB.append(Integer.toString(root.val));
if (root.left == null && root.right == null) { // 当前节点是叶子节点
result.add(pathSB.toString()); // 把路径加入到答案中
} else {
pathSB.append("->"); // 当前节点不是叶子节点，继续递归遍历
// 因为此时的临时路径为 String Buffer类新，需要转换
recur(root.left, pathSB.toString());
recur(root.right, pathSB.toString());
}
}
}
}
理解回溯算法
回溯算法的本质就是递归算法的出口
回溯和递归是一一对应的，有一个递归，就要有一个回溯，这么写的话相当于把递归和回溯拆开了， 一个在花括号里，一个在花括号外。
所以回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！
左叶子之和
关键点在于如何判断
左叶子左叶子就是一个根的左孙子但是下面没有左右子节点,所以我们需要的就是找到一个根 他有左孩子左孩子也有左孩子
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子
即:
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) { 左叶子节点处理逻辑 }
/**
* 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 {
int result = 0;
public int sumOfLeftLeaves(TreeNode root) {
// return recur(root);
return bfs(root);
}
public int bfs(TreeNode root){
if(root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
//从左到右开始
//但是这个题目不需要只需要找到左叶子就好了
if(temp.left != null &&(temp.left.left == null && temp.left.right == null)){
result += temp.left.val;
}
if(temp.left !=null)queue.offer(temp.left);
if(temp.right !=null)queue.offer(temp.right);
}
return result;
}
public int recur(TreeNode root){
if(root == null){
return 0;
}
int leftSum = recur(root.left);
int rightSum = recur(root.right);
int leaf = 0;
if(root.left != null &&(root.left.left == null && root.left.right == null)){
leaf = root.left.val;
}
int sum = leaf +leftSum + rightSum;
return sum;
}
}
找树左下角的值
找深度最大的叶子节点
如果需要遍历整颗树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！
[图片上传失败...(image-cd2175-1649069406096)]
最后需要初始化最小的值
[图片上传失败...(image-e629fe-1649069406096)]
如果是层序便利的化只要是
最后一层的第一次就是我们需要的值
/**
* 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 {
int result ;
int depth = -999 ;
public int findBottomLeftValue(TreeNode root) {
// recur(root,0);
bfs(root);
return result;
}
public void bfs(TreeNode root){
if(root == null){
return ;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0 ; i < size ; i++){
TreeNode temp = queue.poll();
//最后一层的第一个就是我们需要的值
if(i == 0){
result = temp.val;
}
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
}
}
public void recur(TreeNode root,int level){
if(root == null){
return ;
}
//结束条件
if(root.left == null && root.right ==null){
if(level > depth){
depth = level;
result = root.val;
}
}
if(root.left !=null)recur(root.left,level + 1);
if(root.right != null)recur(root.right,level + 1);
}
}
路径总和
主要是
1.
找到路径+返回路径上的值
本题只需要 Boolean的类型
采用
递归的写法3.1.1 `确定函数的参数和类型` 3.1.2 确定`递归的出口` 3.1.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 boolean hasPathSum(TreeNode root, int targetSum) {
// return recur(root,targetSum);
return bfs(root,targetSum);
}
public boolean bfs(TreeNode root,int sum){
if(root == null){
return false;
}
//duilie
Queue<TreeNode> node = new LinkedList<>();
Queue<Integer> sums = new LinkedList<>();
node.offer(root);
sums.offer(root.val);
//从上到下
while(!node.isEmpty()){
int size = node.size();
//从左到右
for(int i = 0 ; i < size ; i++){
TreeNode temp = node.poll();
int count = sums.poll();
if(temp.left == null && temp.right == null && count == sum){
return true;
}
if(temp.left !=null){
node.offer(temp.left);
sums.offer(count + temp.left.val);
}
if(temp.right != null){
node.offer(temp.right);
sums.offer(count + temp.right.val);
}
}
}
return false;
}
public boolean recur(TreeNode root,int sum){
if(root == null){
return false;
}
//找到叶子节点并且当前的值符合sum 找到哦最后了
if(root.left == null && root.right ==null && root.val == sum){
return true;
}
return recur(root.left,sum - root.val)|| recur(root.right,sum - root.val);
}
}
路径总和 II
和上体一样:
这个题需要保存路径需要返回路径的值
. 从中序与后序遍历序列构造二叉树
likou 剑指offer重建二叉树对比
/**
* 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;
* }
* }
*/
public class Solution {
int[] inorder;
int[] postorder;
int postIndex; // 在 postorder 中的 index
HashMap<Integer, Integer> inOrderIndex = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
for (int i = 0; i < inorder.length; i++) {
inOrderIndex.put(inorder[i], i);
}
postIndex = postorder.length - 1;
return buildTreeHelper(0, postorder.length - 1);
}
private TreeNode buildTreeHelper(int left, int right) { // left, right：在 inorder 中的 index
if (left > right) {
return null;
}
int rootVal = postorder[postIndex--];
TreeNode root = new TreeNode(rootVal);
int i = inOrderIndex.get(rootVal);
// 因为采用了 postIndex 每次减一的方法，所以必须先递归生成右子树再递归生成做子树！！！
root.right = buildTreeHelper(i + 1, right);
root.left = buildTreeHelper(left, i - 1);
return root;
}
}
剑指offer15.重建二叉树
终归还是bfs哪个一套的流程很简单
优化问题
[图片上传失败...(image-f125a9-1649069406096)]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
HashMap<Integer, Integer> inMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i = 0; i < inorder.length; i++)
inMap.put(inorder[i], i);
//可以作为参数传递优化内存
return bfs(preorder,0, 0, inorder.length - 1);
}
TreeNode bfs(int[] preorder,int root, int left, int right) {
if(left > right) return null; // 递归终止
TreeNode node = new TreeNode(preorder[root]); // 建立根节点
int dist = inMap.get(preorder[root]); // 找到根节点每次的索引位置
node.left = recur(preorder,root + 1, left, dist - 1); // 开启左子树递归
node.right = recur(preorder,root + dist - left + 1, dist + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
}
附加迭代法:
重建二叉树 - 重建二叉树 - 力扣（LeetCode） (leetcode-cn.com)
方法太过于繁琐,需要维护栈,其实题解使用了安全队列,不建议使用.
最大二叉树
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我们看着来
/**
* 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 TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums,0,nums.length);
}
public TreeNode build(int[] nums,int left,int right){
//左右边界不同结果也会不同
if( left - right ==0){
return null;
}
// 二叉树的根是数组 nums 中的最大元素。
// 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
// 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
int index = max(nums,left,right);
TreeNode root = new TreeNode(nums[index]);//先构建，发现需要个找到“最大元素的地方”
root.left = build(nums,left,index);
root.right = build(nums,index + 1,right);
return root;
}
//需要在数组的全部或者说一侧找到最大数 所以需要范围
public int max(int[] nums,int left,int right){
int index = left;
for(int i = left ; i < right ; i++){
if(nums[i] > nums[index]){
index = i;
}
}
return index;
}
}
合并二叉树
不去推演递归的 具体 输出而是遵循递归的想法来实现如果存在
缺失部分那就左右互换
/**
* 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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
return bfs(root1,root2);
}
public TreeNode dfs(TreeNode root1,TreeNode root2){
if(root1 == null)return root2;
if(root2 == null)return root1;
//不该变原来的俩结构
TreeNode root = new TreeNode(0);
root.val = root1.val + root2.val;
root.left = mergeTrees(root1.left,root2.left);
root.right = mergeTrees(root1.right,root2.right);
return root;
}
public TreeNode bfs(TreeNode root1,TreeNode root2){
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root2);
stack.push(root1);
while (!stack.isEmpty()) {
TreeNode node1 = stack.pop();
TreeNode node2 = stack.pop();
node1.val += node2.val;
if (node2.right != null && node1.right != null) {
stack.push(node2.right);
stack.push(node1.right);
} else {
if (node1.right == null) {
node1.right = node2.right;
}
}
if (node2.left != null && node1.left != null) {
stack.push(node2.left);
stack.push(node1.left);
} else {
if (node1.left == null) {
node1.left = node2.left;
}
}
}
return root1;
}
}
二叉搜索树篇
迭代篇
一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。
对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。
而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。
中间节点如果大于3就向左走，如果小于3就向右走，如图：
[图片上传失败...(image-273139-1649069406096)]
所以迭代法代码如下：
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != NULL) {
if (root->val > val) root = root->left;
else if (root->val < val) root = root->right;
else return root;
}
return NULL;
}
};
第一次看到了如此简单的迭代法，是不是感动的痛哭流涕，哭一会~
class Solution {
// 递归，普通二叉树
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
TreeNode left = searchBST(root.left, val);
if (left != null) {
return left;
}
return searchBST(root.right, val);
}
}
class Solution {
// 递归，利用二叉搜索树特点，优化
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
}
class Solution {
// 迭代，普通二叉树
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
if (pop.val == val) {
return pop;
}
if (pop.right != null) {
stack.push(pop.right);
}
if (pop.left != null) {
stack.push(pop.left);
}
}
return null;
}
}
class Solution {
// 迭代，利用二叉搜索树特点，优化，可以不需要栈
public TreeNode searchBST(TreeNode root, int val) {
while (root != null)
if (val < root.val) root = root.left;
else if (val > root.val) root = root.right;
else return root;
return root;
}
}
二叉搜索树中的搜索
二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
/**
* 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 {
TreeNode result;
public TreeNode searchBST(TreeNode root, int val) {
return recur(root,val);
}
public TreeNode recur(TreeNode root,int val){
if(root == null || root.val == val){
return root;
}
TreeNode left = recur(root.left,val);
TreeNode right = recur(root.right,val);
//充分利用二叉树的性质
result = root.val > val? left : right;
return result;
}
}
