代码随想录 | 二叉树
226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,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 {
public TreeNode invertTree(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
if (root == null) {
return root;
}
que.add(root);
while (!que.isEmpty()) {
int size = que.size();
while (size > 0) {
TreeNode node = que.poll();
TreeNode tmp = new TreeNode();
if (node.right != null && node.left != null) {
//左右孩子都不空，右孩子、左孩子加入队列并交换
que.add(node.right);
que.add(node.left);
tmp = node.right;
node.right = node.left;
node.left = tmp;
} else if (node.right==null&&node.left!=null ) {
que.add(node.left);
node.right=node.left;
node.left=null;
} else if(node.left==null&&node.right!=null){
que.add(node.right);
node.left=node.right;
node.right=null;
}
size--;
}
}
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 {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
//先序遍历
swapChildren(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
ψ(｀∇´)ψ 我的思路
- 层序遍历每一层二叉树，每一层结点的值放入链表，判断链表（除第一层外）是否对称
/**
* 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) {
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (!que.isEmpty()){
int size = que.size();
List<Integer> list = new ArrayList<>();
while (size>0){
TreeNode node = que.poll();
list.add(node.val);//加入链表
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
//判断list是不是对称列表
if(list.size()>1){
Collections.reverse(list.subList(0,list.size()/2));
if(!list.subList(0,list.size()/2).equals(list.subList(list.size()/2,list.size()))){
return false;
}
}
}
return true;
}
}
-
上面的代码并不能判断下面这种情况：
输入：root = [1,2,2,null,3,null,3]
输出：false -
因为只把不空的结点加入到链表，所以上述情况的链表是这样的：[1][2,2][3,3],我想着把null也加入到链表里。不行(x_x)，那样的话就没办法控制临界条件了。
-
下面是代码随想录的递归做法：比较根结点的左右子树是否对称
/**
* 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) {
boolean res = comparable(root.left, root.right);
return res;
}
public static boolean comparable(TreeNode left, TreeNode right){
if(left==null&&right!=null){return false;}
else if(right==null&&left!=null){return false;}
else if(right==null&&left==null){return true;}
else if(right.val!= left.val){return false;}
boolean a = comparable(left.left, right.right);//比较外侧结点
boolean b = comparable(left.right, right.left);//比较内测结点
boolean res = a && b;
return res;
}
}
- 感觉递归的做法要好理解很多，再写两道类似的题目练一下递归
100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
/**
* 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 isSameTree(TreeNode p, TreeNode q) {
//if(p==null&&q==null){return false;}
return comparable(p,q);
}
public boolean comparable(TreeNode p,TreeNode q){
if(p!=null&&q==null){return false;}
else if(p==null&&q==null){return true;}
else if(p==null&&q!=null){return false;}
else if(p.val!=q.val){return false;}
boolean a = comparable(p.left,q.left);
boolean b = comparable(p.right,q.right);
return a && b;
}
}
572. 另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。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 boolean isSubtree(TreeNode root, TreeNode subRoot) {
//前序遍历root
List<TreeNode> nodes = new ArrayList<>();
preorder(root,nodes);
for (TreeNode node : nodes) {
//此时nodes里面是root中的所有结点
if(comparable(node, subRoot)){
return true;
}
}
return false;
}
public void preorder(TreeNode root, List<TreeNode> nodes){
if(root==null){return ;}
nodes.add(root);
preorder(root.left,nodes);
preorder(root.right,nodes);
}
public boolean comparable(TreeNode left,TreeNode right){
if(left==null&&right==null){return true;}
else if(left!=null&&right==null){return false;}
else if(left==null&&right!=null){return false;}
else if(left.val!= right.val){return false;}
boolean a = comparable(left.left, right.left);
boolean b = comparable(left.right, right.right);
return a && b;
}
}
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 {
public int maxDepth(TreeNode root) {
//这里用根结点的高度表示二叉树的最大深度
if(root==null){return 0;}
int leftDepth = maxDepth(root.left);//左孩子的高度
int rightDepth = maxDepth(root.right);//右孩子的高度
return Math.max(leftDepth,rightDepth)+1;//当前结点的高度（左孩子的高度，右孩子的高度的最大值+1）
//后序遍历
}
}
- 感觉递归还是不太好理解
559. N 叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
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 {
public int maxDepth(Node root) {
if(root==null){return 0;}
List<Node> children = root.children;//当前结点的孩子们
int max = 0;
for (Node child : children) {
int depth = maxDepth(child);
max = Math.max(depth,max);
}
return max+1;
}
}
- 扩展成n叉树，和二叉树区别不大，就是孩子数不确定，用for循环遍历求孩子的高度就好
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
ψ(｀∇´)ψ 我的思路
- 稍微改了二叉树最大深度的代码，
/**
* 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 int minDepth(TreeNode root) {
if(root==null){return 0;}//空的结点是第0层(也是递归出口)
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
return Math.min(leftDepth,rightDepth)+1;
}
}
- 代码在运行下图例子时返回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 {
public int minDepth(TreeNode root) {
if(root==null){return 0;}//空的结点是第0层(也是递归出口)
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if(root.left==null){return rightDepth+1;}//如果左子树为空，返回右子树的高度+1
else if(root.right==null){return leftDepth+1;}//如果右子树为空，返回左子树的高度+1
return Math.min(leftDepth,rightDepth)+1;
}
}
222. 完全二叉树的节点个数
完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
ψ(｀∇´)ψ 我的思路
- 层序遍历，每弹出一个数count++
/**
* 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 int countNodes(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
if(root==null){return 0;}
int count = 0;
que.add(root);
while (!que.isEmpty()){
int size = que.size();
while (size>0){
count++;
TreeNode node = que.poll();
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
}
return count;
}
}
- 不知道是不是昨天层序遍历做多了，我现在拿到题想的都是层序遍历，递归好难想啊🤯
class Solution {
// 还是展示递归解法（后序遍历）
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
- 离谱离谱，就这么几行
110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
ψ(｀∇´)ψ 我的思路
- 求出根结点左右子树的最大高度，相减取绝对值不超过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 {
public boolean isBalanced(TreeNode root) {
if(root==null){return true;}
int leftHeight = maxHeight(root.left);
int rightHeight = maxHeight(root.right);
if(Math.abs(leftHeight-rightHeight)<=1){
return true;
} else{return false;}
}
public int maxHeight(TreeNode root){
if(root==null){return 0;}
return Math.max(maxHeight(root.left),maxHeight(root.right))+1;
}
}
- 按我的思路，这就是个平衡二叉树，仔细读题后发现：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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 {
public boolean isBalanced(TreeNode root) {
//后序遍历
int height = getHeight(root);
if(height==-1){return false;}
else return true;
}
public int getHeight(TreeNode root){
if(root==null){
return 0;//null结点高度为0
}
int leftHeight = getHeight(root.left);//左子树的高度
if(leftHeight==-1){return -1;}
int rightHeight = getHeight(root.right);//右子树的高度
if(rightHeight==-1){return -1;}
if(Math.abs(leftHeight-rightHeight)>1){return -1;}//当前结点左右子树高度差>1
return 1+Math.max(leftHeight,rightHeight);//返回当前结点的高度
}
}
- 递归，递归，又是你！！！
257. 二叉树的所有路径
给你一个二叉树的根节点 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 {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();//结果列表
if(root==null){return res;}
List<Integer> path = new ArrayList<Integer>();//路径列表（存放经过结点的值）
postOrder(root,path,res);
return res;
}
public void postOrder(TreeNode node,List<Integer> path,List<String> res){
path.add(node.val);//每一个结点都加在路径里面
if(node.left==null&&node.right==null){//如果node没孩子（叶子节点）
//就可以把path转换成String加到res中啦
StringBuilder sb = new StringBuilder();
for (Integer i : path) {
sb.append(i+"->");
}
String s = sb.toString();
s = s.substring(0,s.length()-2);//把最后一个->去掉
res.add(s);
}
if (node.left != null) {
postOrder(node.left, path, res);
path.remove(path.size()-1);//回溯
}
if (node.right != null) {
postOrder(node.right, path, res);
path.remove(path.size()-1);//回溯
}
}
}
- 这题挺好，标记。
404. 左叶子之和
给定二叉树的根节点 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 {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
int midValue = 0;//存储当前结点的左孩子的值
if(root.left!=null&&root.left.left==null&&root.left.right==null){
midValue = root.left.val;//如果root.left满足左叶子的条件
}
int leftValue = sumOfLeftLeaves(root.left);
int rightValue = sumOfLeftLeaves(root.right);
return midValue+leftValue+rightValue;//返回当前结点的值，加上左右孩子的叶子结点数
}
}
- 递归真的是不好想啊，感觉我现在的水平只能是看懂
513. 找树左下角的值
给定一个二叉树的 根节点 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 {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
List<Integer> list = null;
que.add(root);
while (!que.isEmpty()){//控制层数
list = new ArrayList<>();
int size = que.size();
while (size>0){//控制每层的元素个数
TreeNode node = que.poll();
list.add(node.val);
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
if(size==1){
}
size--;
}
}
return list.get(0);//因为链表每层都刷新，所以此时链表记录的是最后一层的结点
}
}
- hhh，只要可以用层序遍历，我就是小神仙🎈
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
- 感觉和上面的二叉树的所有路径很像，就改了一下上面的代码。第一遍的时候是自己写的，没有写出来。
/**
* 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) {
List<Integer> res = new ArrayList<>();//用来存放所有路径的和
if(root==null){return false;}
List<Integer> path = new ArrayList<Integer>();//用来存放经过结点的值
postOrder(root,path,res);
if(res.contains(targetSum)){return true;}
else return false;
}
public void postOrder(TreeNode node,List<Integer> path,List<Integer> res){
path.add(node.val);//每一个结点的值都加在路径里面
if(node.left==null&&node.right==null){//如果node没孩子（叶子节点）
int sum = 0;
for (Integer i : path) {
sum += i;
}
res.add(sum); //求出当前路径的总和加到res中
}
if (node.left != null) {
postOrder(node.left, path, res);
path.remove(path.size()-1);//回溯
}
if (node.right != null) {
postOrder(node.right, path, res);
path.remove(path.size()-1);//回溯
}
}
}
113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
ψ(｀∇´)ψ 我的思路
- 还是路径的问题，我就按路径的模板写了一下，但是在debug的时候发现res会随着path的改变而改变。活见鬼👻，我明明已经把path加到res里了。
/**
* 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<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();//结果列表
List<Integer> path = new ArrayList<>();//路径列表
if(root==null){return res;}
path(root,path,res,targetSum);
return res;
}
void path(TreeNode node,List<Integer> path,List<List<Integer>> res,int targetSum){
path.add(node.val);
if(node.left==null&&node.right==null){//到达了叶子结点
int sum = 0;
for (Integer i : path) {
sum+=i;
}
if(sum==targetSum){res.add(path);}
}
if (node.left != null) {
path(node.left, path, res, targetSum);
path.remove(path.size()-1);//回溯
}
if (node.right != null) {
path(node.right, path, res, targetSum);
path.remove(path.size()-1);//回溯
}
}
}
- 但仔细一想应该是递归的问题，我找不到解决的方法，看了题解后发现其实就是一行代码
if(sum==targetSum){ res.add(new ArrayList<>(path));}
- 活见鬼👻,刚开始看的时候我就不相信这是java的语法，我就没见过泛型后面的小括号里面放东西😟，但是运行通过。网上也找不到靠谱的解释，我猜是新建了一个与path相同类型的链表把path装了进来，这样我再debug，res就不会随着递归变化了。
❗标记，标记，这一题不太会
106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
确认过眼神，是我写不出来的题目🙂
- 思路是不难理解的，偷个图展示一下
步骤：
- 判断后序数组是否为空
- 取后序数组的最后一个值的下标切割中序数组，把中序数组切割成左中序和右中序
- 用两个区间的长度去切割后序数组，得到左后序和右后序
- 递归（左中序，左后序），递归（右中序，右后序）
/**
* 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 {
Map<Integer, Integer> map; // 方便根据数值查找位置
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
// 参数里的范围都是前闭后开
if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft);
root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
return root;
}
}
- ❗ 标记，标记，这题不是自己写的
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
- 与上一题类似，改了一下上一题的代码
/**
* 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 {
Map<Integer, Integer> map; // 方便根据数值查找位置
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, preorder,0, preorder.length); // 前闭后开
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
// 参数里的范围都是前闭后开
if (inBegin >= inEnd || preBegin >= preEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(preorder[preBegin]); // 找到前序遍历的最后一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定前序数列的个数
root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin+1, preBegin + lenOfLeft+1);
root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenOfLeft+1, preEnd);
return root;
}
}
- 太残忍了，太残忍了，最后这两题，就是在屠杀我的脑细胞💀，不知道看多少集海绵宝宝才能养回来
总结
-
今天的题比昨天的题要好，每一道题都很有代表性😀
-
翻转二叉树：交换结点指向左右孩子的指针
-
对称二叉树：以根结点所在竖直线为对称轴，先比较外侧结点，后比较内侧结点（相同的树，另一棵树的子树类似）（有点像双指针
-
二叉树的最大深度：求二叉树的最大深度就是求根结点的高度，求高度用后序遍历，当前结点的高度是左右孩子高度的最大值+1（N叉树的最大深度类似）
-
二叉树的最小深度：如果左子树为空，当前结点的高度为右子树的高度+1；如果右子树为空，当前结点的高度为左子树的高度+1，画个图你就知道啦🤡
-
完全二叉树的结点个数：基础的遍历题
-
平衡二叉树：求高度的题，要用后序遍历
-
二叉树的所有路径：求路径的题，要用到回溯，需要什么条件就往递归方法中加参数就可
-
左叶子之和：关键是判断左叶子
-
找树左下角的值：层序遍历
-
路径总和：改路径题的模板（其实还是有点迷的，尤其是递归方法带参数，好家伙，那是一个千变万化，根本分析不出来😵）
-
从中/前序后序遍历序列构造二叉树，重点在区间的划分
-
遇到问题总是先想层序遍历，但是感觉递归才是正统解法，要好好掌握递归才行
-
做了一天的二叉树，现在感觉我就是个二叉树🤐
