二叉树总结：
思想简介（开篇先看）
0.什么是前序，中序，后序
前序位置的代码在刚刚进入一个二叉树节点的时候执行；
后序位置的代码在将要离开一个二叉树节点的时候执行；
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。
这个前中后序位置和我们的前中后序遍历有所区别，你可以理解成在前序位置写代码的时候往一个List里面塞元素，那最后得到的就是前序遍历的结果。
- ⼆叉树的所有问题，就是让你在前中后序位置注⼊巧妙的代码逻辑，去达到⾃⼰的⽬的，你只需要单独思考
每⼀个节点应该做什么，其他的不⽤你管，抛给⼆叉树遍历框架，递归会在所有节点上做相同的操作。 。
1.遍历方式的选取
- 设计二叉树的构造，无论时普通二叉树还是二叉搜索树，一定是前序遍历，先构造中间节点
- 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算
- 二叉搜索树的属性，一定是中序，毕竟数组是有序的
- 题目设计到子树，首先想到的是给函数设置返回值；需要遍历完子树才有返回值时，采用后序遍历，如果不需要遍历子树就是前序遍历
遍历二叉树的统一迭代法
class solution{
public List<Integer>preorderTraversal(TreeNode root){
List<Integer>result = new LinkedList<>();
Stack<TreeNode>st =new Stack<>();
if(root!=null){
st.push(root);
}
while(!st.isEmpty()){
TreeNode node=st.peek();
//判断结点是否为空
if(node!=null){
st.pop();//将该节点弹出来，避免重复
if(node.right!=null) st.push(node.right);
if(node.left!=null) st.push(node.left);
st.push(node);
st.push(null);
}
else{
st.pop();//将空结点取出
node = st.peek()；
st.pop();//弹出该结点
result.add(node.val);
}
}
return result;
}
}
层序遍历
//bfs--迭代方式遍历--借助辅助队列--可以从上到下；从左到右，遍历二叉树
class soulution{
public void checkFun02(TreeNode root){
if(root==null){
return;
}
Queue<TreeNode>que = new LinkedList<>();
que.offer(node);
while(!que.isEmpty()){
int len = que.size();
List<Integer>list = new LinkedList<>();
while(len>0){
TreeNode node = que.poll();
list.add(node.val);
if(node.left!=null){
que.offer(node.left);
}
if(node.right!=null){
que.offer(node.right);
}
len--;
}
relist.add(list);
}
}
}
递归DFS遍历二叉树:(前序，中序，后序)
class solution{
List<Integer>result = new ArrayList<>();
public List<Integer>preorderTraverse(TreeNode root){
traverse(root);
return result;
}
public void traverse(TreeNode root){
if(root==null){
return;
}
//递归的逻辑，处理中间结点
result.add(root.val);
traverse(root.left);
traverse(root.right);
}
}
二叉树的属性
1.最大深度，最小深度
//前序遍历深度--才是真正求深度的逻辑;这里采用后序
class solution{
public int maxDepth(TreeNode root){
if(root==null){
return 0;
}
int leftDepth =maxDepth(root.left);
int rightDepth = maxDepth(root.right);
retrun math.max(leftDepth+rightDepth+1);
}
}
//最小深度，也即是求最短路径，BFS,当节点没有子节点的时候
class solution{
public int minDepth(TreeNode root){
if(root==null){
return 0;
}
Deque<TreeNode>que = new LinkedList<>();
que.offer(root);
int depth=0;
while(!que.isEmpty()){
int len = que.size();
depth++;
for(int i=0;i<len;i++){
TreeNode node = que.poll();
if(node.left==null&&node.right==null){
return depth;
}
if(node.left!=null){
que.offer(node.left);
}
if(node.right!=null){
que.offer(node.right);
}
}
}
retrun depth;
}
}
2.二叉树是否对称
判断一个节点的左子树的左节点是否等于右子树的右节点，因为需要进行两两比较，采用后序遍历
- 以一为分界限，分为左子树和右子树，左子树的节点和右子树的节点相等才行，也就是比较两个树
class solution{
public boolean isSymmetric(TreeNode root){
return compare(root.left,root.right);
}
boolean compare(TreeNode left,TreeNode right){
//当遇到以下情况返回false，排除空节点的情况
if(left==null || right==null){
return false;
}
if(left==null && right==null){
return true;
}
if(left.val!=right.val){
return false
}
boolean outside=compare(left.left,right.right);
boolean inside =compare(left.right,right,left);
return outside&&inside;
}
}
3.二叉树结点个数
给你一个完全的二叉树，求出该树的节点个数
- 层序遍历肯定是可以解决的
- 递归遍历是采用后序
//通用递归法：
class solution{
public int countNodes(TreeNode root){
if(root==null){
return 0;
}
//记录左子树节点数
int left=countNode(root.left);
//记录右子树节点数
int right=count(root.right);
//返回节点数
return left+right+1;
}
}
4.二叉树是否平衡
4.1平衡二叉树：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
二叉树的深度与高度(110)
深度是指根节点到该节点的最长简单路径边的条数，也就是while循环从1上往下
高度：指该节点到叶子节点的最长简单路径边的条数，有点从下往上数
class solution{
public boolean isBalanced(TreeNode root){
maxDepth(root);
return flag;
}
boolean flag = true;
public int maxDepth(TreeNode root ){
if(root==null){
retrun 0;
}
//遍历左右
int leftDepth=maxDepth(root.left);
int rightDepth = maxDepth(root.right);
//进行绝对值判断
if(Math.abs(rightDepth-leftDepth)>1){
flag=false;
}
return Math.max(rightDepth+leftDepth+1);
}
}
5.二叉树的找路径(257)
- 递归中带着回溯，回溯就是用来记录路程的
class sulution{
public List<Stirng>binaryTreePaths(TreeNode root){
List<String>result = new ArrayList<>();
if(root==null){
return result;
}
Stack<Object>satck = new Stack<>();
stack.push(root);
stack.push(root.val+"");
while(!stack.isEmpty()){
//进行节点与路径同时出栈
String path =(String)stack.pop();
TreeNode node=(TreeNode)stack.pop();
//这是将路径存进去的判断条件
if(node.left==null&&node.right==null){
//将路径加进去
result.add(path);
}
//右子节点不为空
}if(ndoe.right!=null){
stack.push(node.right);
stack.push(path+"->"+root.right.val);
}
//左子节点不为空
if(node.left!=null){
stack.push(node.left);
stack.push(path+"->"+root.left.val);
}
return result;
}
}
6.二叉树的左子叶之和（404）
- 这里可以采用层序遍历，也可以用traverse递归来遍历，左子节点就是root.left!=null,下面的左右节点为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 {
public int sumOfLeftLeaves(TreeNode root) {
traverse(root);
return sum;
}
int sum = 0;
void traverse(TreeNode root){
if(root==null){
return;
}
if (root.left != null &&
root.left.left == null && root.left.right == null) {
// 找到左侧的叶子节点，记录累加值
sum += root.left.val;
}
traverse(root.left);
traverse(root.right);
}
}
7.二叉树的左下角之和（513）
class Solution {
public int findBottomLeftValue(TreeNode root) {
if(root==null){
return 0;
}
Queue<TreeNode>que = new LinkedList<>();
que.offer(root);
int res = 0;
while(!que.isEmpty()){
int size = que.size();
for(int i = 0;i<size;i++){
TreeNode node = que.poll();
if(i==0){
res = node.val;
}
if(node.left!=null){
que.offer(node.left);
}
if(node.right!=null){
que.offer(node.right);
}
}
}
return res;
}
}
8，二叉树的路径之和（112、113）
-
112路径之和的判断，当我们递归到叶子节点的，来判断最后root.val==sum;我们的递归就是进行左右子树递归，递归过程中进行sum-root.val操作
113的路径之和代表了回溯算法，和112不一样的是，我们需要对路径之和的点进行记录，也即是到子叶节点了，就要将path路径的点存进集合
回溯算法就是需要先处理节点，在进行递归，先addLast(),在removeLast();
class solution{
public boolean haspathsum(TreeNode root,int target){
if(root==null){
return false;
}
//代表以及到了子叶节点
if(root.left==null&&root.right==null){
return root.val==target;
}
return haspathsum(root.left,target-root.val)||haspathsum(root.right,target-root.val);
}
}
//113T,
class Solution {
List<List<Integer>>res = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root==null){
return res;
}
helper(root,targetSum,new LinkedList<>());
return res;
}
private void helper(TreeNode root,int targetSum,LinkedList<Integer>path){
//path用来记录节点数据
if(root==null) return;
int remain = targetSum-root.val;
//进行节点的处理
if(root.left==null && root.right==null){
if(remain==0){
path.addLast(root.val);
res.add(new LinkedList<>(path));
path.removeLast();
}
return;
}
path.addLast(root.val);
helper(root.left,remain,path);//这个就是target-root.val;
path.removeLast();
path.addLast(root.val);
helper(root.right,remain,path);
path.removeLast();
}
}
9.三叉树的遍历模式
用一个traverse函数对左右节点进行处理，遍历，需要连接左右节点，以及兄弟节点
基槽：node1.next = node2
if(root==null){
return;
}
traverse(root.left;root.right);
return root;
void traverse(TreeNode node1,TreeNode node2){
if(root==null){
return;
}
node1.next =node2;//核心代码
traverse(node1.left,node1.right);
traverse(node2.left,node2.right);
//连接兄弟节点
traverse(node1.right;node2.left);
return root;
//进行三叉树的遍历
}
10.二叉树的直径(543)
- 后序遍历，因为我们算出左右的直径后加上根结点的直径就是最大的
class Solution {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
int maxDepth(TreeNode root){
if(root==null){
return 0;
}
int leftMaxDepth = maxDepth(root.left);
int rightMaxDepth = maxDepth(root.right);
//计算下最大直径
int myDiameter = leftMaxDepth+rightMaxDepth;
maxDiameter = Math.max(myDiameter,maxDiameter);
return 1+Math.max(leftMaxDepth,rightMaxDepth);
}
}
11.二叉树的最大路径总和(124)
- 这题需要用到二叉树的后序遍历，在这之前我们已经做过最大直径和寻找二叉树的节点和，他们有一个共性就是的需要计算对应子树的值
- MathDepth是我们计算其深度，而直径就是在深度的后序遍历上加上计算直径，这一题首先左右子树的计算和可能有负数，因此要在Math.max(0,left)中添加一个0，其次我们最大路径和应该是left+right+根结点值，最后返回的还是oneSideMax值，也就是左右子树的最大值加根结点
class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root==null){
return 0;
}
oneSideMax(root);
return res;
}
int oneSideMax(TreeNode root){
if(root==null) return 0;
int leftMaxSum = Math.max(0,oneSideMax(root.left));//如果子树路径的和为负，我们需要置为0
int rightMaxSum = Math.max(0,oneSideMax(root.right));
int pathMaxSum = root.val+ leftMaxSum+rightMaxSum; //该节点以及左右子树的节点和
res = Math.max(pathMaxSum,res);//判断左右子树的路径是否大于现在的路径和
//左右子树最大单边和加上根结点值
return Math.max(leftMaxSum,rightMaxSum)+root.val;
}
}
12.合并二叉树（617）
- 我们对节点只需要进行叠加就性，当其中一个为空，我们返回剩下的树即可
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
root1.val+=root2.val;
root1.left = mergeTrees(root1.left,root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
}
二叉树的修改与改造
1.翻转二叉树(226)
- 翻转我们可以知道就是将子树的left和right进行交换
- 可以通过遍历，也可以用分解的方法来做
//1.遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
traverse(root);
return root;
}
void traverse(TreeNode root){
if(root==null){
return;
}
TreeNode temp = null;
temp = root.left;
root.left = root.right;
root.right = temp;
traverse(root.left);
traverse(root.right);
}
}
//2.递归
class solution{
public TreeNode invertTree(TreeNode root){
TreeNode left,right;
if(root==null) return null;
left = invertTree(root.left);
right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
1.1填充每个节点的下一个右侧指针节点(116)
- 思路，看成一个三叉树，每次都是节点的left->right
class Solution {
public Node connect(Node root) {
if(root==null) return null;
traverse(root.left,root.right);
return root;
}
void traverse(Node node1,Node node2){
if(node1==null || node2==null){
return;
}
node1.next = node2;
traverse(node1.left,node1.right);
traverse(node2.left,node2.right);
traverse(node1.right,node2.left);
}
}
1.2二叉树展开为链表（114）
这一个需要理解递归，flatter自动帮我们把链表拉直，因此我们只需要拉直后，将左值针置为null，root.right = left就代表左子树的已经迁移过来了
其次我们需要将原右子树的放在当前右子树下面，代表我们需要一个遍历到当前右子树下面，在用p.right = right就可以了
class Solution {
// 定义：将以 root 为根的树拉平为链表
public void flatten(TreeNode root) {
// base case
if (root == null) return;
// 先递归拉平左右子树
flatten(root.left);
flatten(root.right);
/****后序遍历位置****/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;
// 2、将左子树作为右子树
root.left = null;
root.right = left;
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
p.right = right;
}
}
2.构造二叉树
//构造模板
HashMap<Integer,Integer>map = new HashMap<>();
public TreeNode bulidTree(int[]preorder,int[]inorder){
for(int i=0;i<inorder.length;i++){
map.put(nums[i],i);
}
return build(preorder,0,num.length,inorder,0,nums.length);
}
/*
构造二叉树，返回根结点
*/
TreeNode build(int[]preorder,int preStart,int preEnd
,int[]inorder,int inStart,int inEnd){
int rootVal = preorder[preStart];
int index = inorder[rootVal];
int leftSize = index-inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(preorder,?,?,inorder,?,?);
root.right = build(preorder,?,?,inorder,?,?);
retrun root;
}
- ⼆叉树的构造问题⼀般都是使⽤「分解问题」的思路：构造整棵树 = 根节点 + 构造左⼦树 + 构造右⼦树
3.1最大二叉树（654）
- 构造二叉树需要直到root节点，其次就是root.left,root.right等相关的问题，同时左右子树都是根据递归来的，因此不能直接将其划分为左右；
- 我们知道题目给定了对应的最大值作为根结点，那么实际上我们递归时，左右子树的范围，每一个范围都有一个子节点，因此在for循环的时候；
- int i = lo;lo <hi就是递归的精髓
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums,0,nums.length-1);
}
TreeNode build(int[]nums,int lo,int hi){
if(lo > hi){
return null;
}
int index = -1,maxVal = Integer.MIN_VALUE;
for(int i = lo;i<=hi;i++){
if(maxVal < nums[i]){
index = i;
maxVal = nums[i];
}
}
TreeNode root = new TreeNode(maxVal);
root.left = build(nums,lo,index-1);
root.right = build(nums,index+1,hi);
return root;
}
}
3.2从前序和中序构造二叉树（105）
- 由前序和中序的遍历特点有如下特点
/**
* 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 {
HashMap<Integer,Integer>valueOfIndex = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
//将遍历的中序值存到map集合
for(int i = 0;i<inorder.length;i++){
valueOfIndex.put(inorder[i],i);
}
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode build(int[]preorder,int preStart,int preEnd,int[]inorder,int inStart,int inEnd){
if(preStart>preEnd){
return null;
}
//记录第一个结点元素，就是前序遍历的首字母
int rootVal= preorder[preStart];
//2.记录该节点在中序的索引，并切割中序
int index = valueOfIndex.get(rootVal);
//3.记录该左子树的位置
int leftSize = index-inStart;
//4.构造出根结点
TreeNode root = new TreeNode(rootVal);
//5.递归构造左右子树
root.left = build(preorder,preStart+1,preStart+leftSize,inorder,inStart,index-1);
root.right= build(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inEnd);
return root;
}
}
3.3；从中序和后序进行遍历构造二叉树(106)
/**
* 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 {
HashMap<Integer,Integer>map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
//后序的最后一位是根节点
for(int i=0;i<inorder.length;i++){
map.put(inorder[i],i);
}
return build(inorder,0,inorder.length-1,
postorder,0,postorder.length-1);
}
TreeNode build(int[]inorder,int inStart,int inEnd,int[]postorder,int postStart,int postEnd){
//终止条件
if(inStart>inEnd){
return null;
}
int rootval = postorder[postEnd];
//找到根结点的索引值、
int index = map.get(rootval);
int leftSize = index-inStart;
TreeNode root = new TreeNode(rootval);
root.left = build(inorder,inStart,index-1,postorder,postStart,postStart+leftSize-1);
root.right = build(inorder,index+1,inEnd,postorder,postStart+leftSize,postEnd-1);
return root;
}
}
二叉搜索树的属性(增删改查)
//对于二叉搜素树的常见模式
void BST(TreeNode root,int target){
if(root.val==target){
//做点什么操作
}
if(root.val>target){
BST(root.left,target);
}
if(root.val<target){
BST(root.right,target);
}
}
1.二叉搜索树中的搜索（98）
- 验证是否是一个正确的二叉搜索树，我们需要的是【根结点要比左子树的任何结点都大，比右子树的任何结点都小】；也就是在遍历左子树的时候要也要有根结点和左子树的最小值啥的
- 类似于BST(root.left,min,root);而我们的函数就是BST(TreeNode root,int min,int max);
- 条件就是（min!=null && root.val<=min.val)return false;
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
// 限定左子树的最大值是 root.val，右子树的最小值是 root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
}
2.求二叉搜索树的最小绝对差(530)
-
当涉及到二叉树的插值时，我们可以声明一个TreeNode prev记录上一个节点的值，因此这样的话我们利用中序遍历就可以进行相减
class Solution { public int getMinimumDifference(TreeNode root) { traverse(root); return res; } TreeNode prev = null; int res = Integer.MAX_VALUE; //遍历函数 void traverse(TreeNode root){ if(root==null){ return; } traverse(root.left); if(prev!=null){ res = Math.min(res,root.val-prev.val); } prev = root; traverse(root.right); } }
3.求二叉搜索树的众数（501）
- 众数需要的是我们利用最小绝对插值的方法，利用搜索树的特性，我们将其进行中序遍历
- 我们pre记录前一个节点，当pre==rootVal的时候count++，再来比对count>MaxCount or == maxCount;
class Solution {
//众数有多个
ArrayList<Integer>resList;
int maxCount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
resList = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
findMode1(root);
int[]res = new int[resList.size()];
for(int i = 0;i<resList.size();i++){
res[i] = resList.get(i);
}
return res;
}
public void findMode1(TreeNode root){
if(root==null){
return;
}
findMode1(root.left);
int rootVal = root.val;
//当pre ！= rootVal 或者为空那么count就是只有一个
if(pre==null || rootVal!=pre.val){
count = 1;
}else{
count++;
}
//更新结果集
if(count>maxCount){
resList.clear();
resList.add(rootVal);
maxCount = count;
}else if(count==maxCount){ //值相等的时候
resList.add(rootVal);
}
pre = root;
findMode1(root.right);
}
}
4.二叉搜索树转成累加树（538）
只需要对于中序遍历后的节点进行累加即可
class Solution {
public TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
int sum = 0;
void traverse(TreeNode root){
if(root==null){
return;
}
traverse(root.right);
//中序遍历是将节点进行累加
sum+=root.val;
root.val = sum;
traverse(root.left);
}
}
5.二叉搜索树中的第k小的元素（230）
- 二叉搜索树是一个中序遍历的结果，规定左子树的节点是要小于中间节点，右子树的节点是要大于中间节点，这就是BST的最大特点，是一个升序的节点
- 那么对于这题我们只需要中序遍历的时候判断k==rank(第几次的遍历)->对应返回响应的root.val
class Solution {
public int kthSmallest(TreeNode root, int k) {
traverse(root,k);
return res;
}
int res = 0;
int rank = 0;
void traverse(TreeNode root,int k){
if(root==null){
return ;
}
traverse(root.left,k);
rank++;
if(rank==k){
res = root.val;
}
traverse(root.right,k);
}
}
二叉树的公共祖先问题
1.二叉树的公共祖先
递归的basecase:
如果root==null 那么说明不在
如果root==p/root==q就代表着，pq最近的公共祖先就是root;
进行递归
TreeNode left;TreeNode right;
//此时又分四种情况
如果left,right==null 说明没有找到
如果left!=null && right!=null,那么说明p,q在左右子树里面，最近的祖先就是root
如果left==null,right！=null,说明最近的组先在right里面，祖先指向root
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(root==p || root==q) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
//如果p\q都在root根结点的树中
if(left!=null && right != null){
return root;
}
//如果p\q都不在的话，返回Null
if(left==null && right==null){
return null;
}
//如果p和q只有一个在root为根的树中，函数返回该节点；
return left==null? right: left;
}
}
2.二叉搜索树的公共组先问题
//根据搜索树的特点，根结点比左边大比右小，只需要root.val和p,q进行对比就可以
class solution{
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
if(root==null){
return null;
}
if(p.val >q.val){
return lowestCommAncestor(root,q,p);
}
if(root.val >= p.val && root.val <= q.val){
return root;
}
if(root.val >q.val){
return lowerCommonAncestor(root.left,p,q);
}else{
return lowerCommonAncestor(root.right,p,q);
}
}
}
//解法二：
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
二叉搜索树的修改与构造
1.二叉搜索树的插入操作
对二叉树的遍历就是找的过程，访问就是改的过程
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
return new TreeNode(val);
if (root.val < val){
root.right = insertIntoBST(root.right, val); // 递归创建右子树
}else if (root.val > val){
root.left = insertIntoBST(root.left, val); // 递归创建左子树
}
return root;
}
}
2.二叉搜索树的删除操作（450）
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
/**
进行删除的话，先找到是左还是右，再根据root.val==key进行删除
*/
if(root==null){
return null;
}
if(root.val>key){
root.left = deleteNode(root.left,key);
}
if(root.val < key){
root.right = deleteNode(root.right,key);
}
//当处理到删除节点的适合
if(root.val == key){
//1.左子树为null
if(root.left==null){
return root.right;
}
//2.右子树为Null
if(root.right==null){
return root.left;
}
//3.左右子树不为Null,获得右子树最小值
TreeNode minNode = getMin(root.right);
//删除右子树的最小值(因为删除最小值了之后就只有root.right)
root.right = deleteNode(root.right,minNode.val);
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
}
return root;
}
//找到右子树最小的左节点
TreeNode getMin(TreeNode node){
while(node.left!=null){
node = node.left;
}
return node;
}
}
3.二叉搜索树的修剪操作
669.二叉树的修剪
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root==null){
return null;
}
if(root.val < low){
//删除左边的，返回右子树
return trimBST(root.right,low,high);
}
if(root.val > high){
//删除右边的，返回左子树
return trimBST(root.left,low,high);
}
//闭区间[lo.hi]内节点什么都不做
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
return root;
}
}
4.二叉搜索树的构造（95，96）
思路:动态规划
假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数
即有:G(n) = f(1) + f(2) + f(3) + f(4) + … + f(n)
n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,…,i-1]，右子树节点个数为[i+1,i+2,…n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
上面两式可得:G(n) = G(0)G(n-1)+G(1)(n-2)+…+G(n-1)*G(0)
在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素，从1遍历到i为止。
所以递推公式：dp[i] += dp[j – 1] * dp[i – j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
class Solution {
public int numTrees(int n) {
int[]dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i =2;i<=n;i++){
for(int j = 1;j<=i;j++){
dp[i]+=dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}
4.1二叉树的序列化与反序列化（297）
序列化就是树变成字符串，反序列化就是字符串变成树的结构；
- 1.前序遍历
public class Codec {
String SEP = ",";
String NULL = "#";
/* 主函数，将二叉树序列化为字符串 */
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
/* 辅助函数，将二叉树存入 StringBuilder */
void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
/******前序遍历位置******/
sb.append(root.val).append(SEP);
/***********************/
serialize(root.left, sb);
serialize(root.right, sb);
}
/* 主函数，将字符串反序列化为二叉树结构 */
public TreeNode deserialize(String data) {
// 将字符串转化成列表
LinkedList<String> nodes = new LinkedList<>();
for (String s : data.split(SEP)) {
nodes.addLast(s);
}
return deserialize(nodes);
}
/* 辅助函数，通过 nodes 列表构造二叉树 */
TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty()) return null;
/******前序遍历位置******/
// 列表最左侧就是根节点
String first = nodes.removeFirst();
if (first.equals(NULL)) return null;
TreeNode root = new TreeNode(Integer.parseInt(first));
/***********************/
root.left = deserialize(nodes);
root.right = deserialize(nodes);
return root;
}
}
4.2.寻找重复的子树（652）
class Solution {
//记录子树出现的次数
HashMap<String,Integer>memo = new HashMap<>();
//记录重复子树的根结点
LinkedList<TreeNode>res = new LinkedList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
//经行序列化，转成String类型
traverse(root);
return res;
}
String traverse(TreeNode root){
if(root==null){
return "#";
}
//采用后序遍历
String left = traverse(root.left);
String right = traverse(root.right);
String subTree = left+","+right+","+root.val;
//记录子树出现的次数
int freq = memo.getOrDefault(subTree,0);
if(freq==1){
res.add(root);
}
memo.put(subTree,freq+1);
return subTree;
}
}
5.二叉搜索子树的最大键值和（1373）
思路：
1.我们需要判断概述是否是BST，如果不=是就能算
2.计算出左子树的最大值和右子树的最小值（用于和root相比较来判断是否是BST)
3.左右子树的节点值之和
- 这里采用数组维护，因为可以避免调用多个递归，new int[4],res[0]=1就代表是BST,res[1]=Integer.Max_Value代表左子树的最大值，res[2] = Integer.MIN_VALUE,res[3] = 0代表我们的累加和
class Solution {
int maxSum = 0;
public int maxSumBST(TreeNode root) {
traverse(root);
return maxSum;
}
public int[] traverse(TreeNode root){
//res[0]=1是代表是BST RES[1]代表最小值，res[2]最大值，res[3]代表和
if(root==null){
return new int[]{1,Integer.MAX_VALUE,Integer.MIN_VALUE,0};
}
int[]left = traverse(root.left);
int[]right = traverse(root.right);
int[]res = new int[4];
if(left[0]==1 && right[0]==1 && root.val>left[2] && root.val<right[1]){
res[0] = 1;
//计算以根节点的最小值
res[1] = Math.min(left[1],root.val);
res[2] = Math.max(right[2],root.val);
res[3] = left[3]+right[3]+root.val;
maxSum = Math.max(res[3],maxSum);
}else{
res[0] = 0;
}
return res;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/101992.html
