树相应的基础知识
节点表达方式
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
} 1. 树的深度
递归求取左右字数的深度，返回两者中的较大者并加1，即为树的深度。
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
public int maxDepth (TreeNode root) {
// write code here
if (root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth,rightDepth);
}
} 2. 树的层次遍历(以层为单位输出)
面试真题
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
输出形式为：[[3],[9,20],[15,7]]
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root != null){
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
//遍历的时候加入结果集也是可以的，而且更简洁
ArrayList<Integer> newLevel = new ArrayList<>();
for (int i = 0;i < size;i ++){
TreeNode top = queue.poll();
newLevel.add(top.val);
if(top.left != null) queue.offer(top.left);
if(top.right != null) queue.offer(top.right);
}
result.add(newLevel);
}
}
return result;
}
} 3. 二叉搜索树中第k个节点
面试真题
给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，
按结点数值大小顺序第三小结点的值为4
陷进 ：此题需要针对k的大小进行分析
public class Solution {
ArrayList<TreeNode> array = new ArrayList<>();
TreeNode KthNode(TreeNode pRoot, int k){
inOrder(pRoot);
if(k >= 1 && array.size()>=k) {
return array.get(k-1);
}
return null;
}
public void inOrder(TreeNode pRoot){
if(pRoot != null){
inOrder(pRoot.left);
array.add(pRoot);
inOrder(pRoot.right);
}
}
} 4. 二叉树的最大路径和
面试真题
给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点。
例如：
给出以下的二叉树
返回的结果为6
public class Solution {
//这道题目自己有两个误区：
//1个是没有把握到这里的路径还是可以左+根+右这样的曲的路径。
//2个是：在包含负数的处理过程中没有意识到如果是负数直接摒弃掉就可以了，因为最后反正都是抵消的因子
//还有一定就是 我们用一个共享的变量记录了最大值，所以这个时候我们在递归的时候不需要关心如果不以子节点作为路径中一个元素时此时的最大值是什么，
//因为如果是最大的，那么在遍历的过程值一定会记录到maxValue中的。
int maxValue = Integer.MIN_VALUE;
public int help(TreeNode root){
if(root == null)return 0;
int left = help(root.left);
int right = help(root.right);
maxValue = Math.max(maxValue, Math.max(0,left) + root.val + Math.max(0,right));
return Math.max( Math.max(0,left) + root.val, Math.max(0,right)+root.val);
}
public int maxPathSum(TreeNode root) {
if(root == null)return 0;
//if(root.left == null && root.right == null)
help(root);
return maxValue;
}
} 5. 在二叉树中找到两个节点的最近公共祖先
面试真题
给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
import java.util.*;
public class Solution {
/**
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
// write code here
return CommonAncestor(root,o1,o2).val;
}
public TreeNode CommonAncestor(TreeNode root,int o1,int o2){
if(root == null || root.val == o1 || root.val == o2){
return root;
}
TreeNode left = CommonAncestor(root.left,o1,o2);
TreeNode right = CommonAncestor(root.right,o1,o2);
if(left == null) return right; //都在右侧
if(right == null) return left; //都在左侧
return root; //在左右两侧
}
} 6. 判断一棵二叉树是否为一颗搜索二叉树和完全二叉树
面试真题
题目描述：给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。
输入 {2,1,3}
输出 {true,true}
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
public boolean[] judgeIt (TreeNode root) {
// write code here
//返回结果的boolean数组
return new boolean[]{isBST(root),isCompleteTree(root)};
}
//一棵树如果是搜索二叉树，则中序遍历一定有序
private TreeNode pre;
public boolean isBST(TreeNode root){
if(root == null) return true;
if(!isBST(root.left)){
return false;
}
if(pre != null && pre.val >= root.val){
return false;
}
pre = root; //前一个输出节点
if(!isBST(root.right)){
return false;
}
return true;
}
//层次遍历遇到第一个空节点后，剩余的节点中如还有非空，则一定不是，（允许每一层中最有节点可以为空）
public boolean isCompleteTree(TreeNode root){
if(root == null) return true;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
boolean notComplete = false;
while (!queue.isEmpty()){
TreeNode temp = queue.remove();
if(temp == null){
//第一次遇到空节点，改变状态，执行下一个节点
notComplete = true;
continue;
}
if(notComplete){ //自出现第一个空节点后，出现了非空节点，直接返回false
return false;
}
queue.add(temp.left);
queue.add(temp.right);
}
return true;
}
} 7. 二叉树根节点到叶子节点的所有路径和
面试真题
题目描述：给定一个仅包含数字 0−9\ 0-9 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是1→2→31\to 2\to 31→2→3,那么这条路径就用 123\ 123 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：
这颗二叉树一共有两条路径，
根节点到叶子节点的路径 1→21\to 21→2 用数字 12\ 12 12 代替
根节点到叶子节点的路径 1→31\to 31→3 用数字 13\ 13 13 代替
所以答案为 12+13=25\ 12+13=25 12+13=25
import java.util.*;
public class Solution {
/**
* @param root TreeNode类
* @return int整型
*/
public int sumNumbers (TreeNode root) {
// write code here
if(root == null) return 0;
int sum = 0;
return preOrder(root,sum);
}
//先序遍历的变型。
public int preOrder(TreeNode root,int sum){
if(root == null) return 0;
sum = 10 * sum + root.val;
//如果左右节点都为空时返回根节点的值
if(root.left == null && root.right == null) return sum;
return preOrder(root.left,sum) + preOrder(root.right,sum);
}
} 8. 二叉树层次遍历变形
面试真题
题目描述：给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树之字形层序遍历的结果是
[
[3],
[20,9],
[15,7]
]
public class Solution {
/**
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
private Queue<TreeNode> queue = new LinkedList();
private boolean flag = true;
public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(root == null)return result;
queue.add(root);
while (!queue.isEmpty()){
int size = queue.size();
ArrayList<Integer> newLevel = new ArrayList();
for (int i = 1;i <= size;i ++){
TreeNode temp = queue.poll();
if(flag) newLevel.add(temp.val); //正向添加
else newLevel.add(0,temp.val); //反向添加
//向队列中添加孩子节点
if(temp.left != null) queue.offer(temp.left);
if(temp.right != null) queue.offer(temp.right);
}
flag = !flag;
result.add(newLevel);
}
return result;
}
} 9. 判断t1树中是否有与t2树拓扑结构一样的子图
面试真题
题目描述： 给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 等于 E1 ，则表示 t1 树和t2 树的拓扑结构完全相同。
输入 ： {1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}
输出 ： true
public class Solution {
/**
* @param root1 TreeNode类
* @param root2 TreeNode类
* @return bool布尔型
*/
public boolean isContains (TreeNode root1, TreeNode root2) {
// write code here
if(root1 == null || root2 == null) return false;
boolean flag = false;
if(root1.val == root2.val) return isSubTree(root1,root2);
if(!flag) flag = isContains(root1.left,root2);
if(!flag) flag = isContains(root1.right,root2);
return flag;
}
public boolean isSubTree(TreeNode root1, TreeNode root2){
//空树是所有树的子树，但是任何非空树都不是空树的子树
if(root2 == null) return true;
if(root1 == null) return false;
if(root1.val != root2.val) return false;
return isSubTree(root1.left,root2.left) && isSubTree(root1.right,root2.right);
}
} 10. 序列化和反序列化二叉树
面试真题
题目描述： 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树
理解：这里采用了层次遍历来对二叉树进行序列化和反序列化的过程，序列化可理解为对二叉树进行层次遍历，而反序列化就是将层次遍历的
输出重新构建二叉树。
public class Solution {
//通过层次遍历来序列化
String Serialize(TreeNode root) {
StringBuffer result = new StringBuffer("");
if(root != null){
result.append(String.valueOf(root.val)); //现将根节点存放到序列化的字符串中
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode head = queue.poll();
//如果左右节点存在空，将用 # 进行代替，不为空则正常添加
if(head.left == null){
result.append(",#");
} else {
result.append("," + String.valueOf(head.left.val));
queue.offer(head.left);
}
if(head.right == null){
result.append(",#");
} else {
result.append("," + String.valueOf(head.right.val));
queue.offer(head.right);
}
}
}
return result.toString();
}
//对数的层次遍历来反序列化
TreeNode Deserialize(String str) {
TreeNode root = null;
if(!str.equals("")){
String[] list = str.split(",");
int index = 1;
root = new TreeNode(Integer.parseInt(list[0])); //将根节点反序列化回去
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty() && index < list.length){
//往回反序列时，也是左右节点一起
TreeNode temp = queue.poll();
if(!list[index].equals("#")){
TreeNode newLeft = new TreeNode(Integer.parseInt(list[index]));
temp.left = newLeft;
index ++;
queue.offer(newLeft);
} else index ++; //为空节点是不做处理，但是需要将其索引加 1；
if(index < list.length && !list[index].equals("#")){
TreeNode newRight = new TreeNode(Integer.parseInt(list[index]));
temp.right = newRight;
index ++;
queue.offer(newRight);
} else index ++;
}
}
return root;
}
} 11. 平衡二叉树
面试真题
题目描述： 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) return true;
if(Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1)
return false;
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int TreeDepth(TreeNode root){
//根为空，返回 0
if(root == null) return 0;
//如果根为叶子节点，那么返回根的深度 1
if(root.left == null && root.right == null) return 1;
//反之返回左右子树深度较大值 + 1
return 1 + Math.max(TreeDepth(root.left),TreeDepth(root.right));
}
} 12. 二叉树的镜像
面试真题
题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：源二叉树
public class Solution {
public void Mirror(TreeNode root) {
if(root == null)
return ;
if(root.left == null && root.right == null)
return ;
//交换左右子树
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
//递归给两个子树进行左右子树镜像
if(root.left != null)
Mirror(root.left);
if(root.right != null)
Mirror(root.right);
}
} 13. 路径总和
力扣112.路径总和
题目描述：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
给定如下二叉树，以及目标和 sum = 22
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
// 到达叶子节点时，递归终止，判断 sum 是否符合条件。
if (root.left == null && root.right == null) {
return root.val == sum;
}
// 递归地判断root节点的左孩子和右孩子。
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
} 升级版：输出所有满足条件的路径
例如：sum = 22
输出：[[5,4,11,2],[5,8,4,5]]
注意点：当 conut == 0 是虽然path中已经是其中的一条路径，但不能直接把path直接加入到result中
因为这样添加的只是 path的地址,内部的值其实一直在变化
if(root.left == null && root.right == null){ //遇到叶子节点需要返回
if(count == 0){//如果total=0说明该路径符合要求
result.add(path);
}
return;
} 错误输出： [[5][5]]
AC代码
class Solution {
List<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
public void traversal(TreeNode root,int count){
if(root != null){
if(root.left == null && root.right == null){ //遇到叶子节点需要返回
if(count == 0){
ArrayList<Integer> temp = new ArrayList<>();
temp.addAll(path);
result.add(temp); //如果total=0说明该路径符合要求
}
return;
}
if (root.left != null) { // 左 （空节点不遍历）
path.add(root.left.val);
count -= root.left.val;
traversal(root.left,count); // 递归
count += root.left.val; // 回溯
path.remove(path.size() - 1); // 回溯
}
if (root.right != null) { // 右 （空节点不遍历）
path.add(root.right.val);
count -= root.right.val;
traversal(root.right, count); // 递归
count += root.right.val; // 回溯
path.remove(path.size() - 1); // 回溯
}
return ;
}
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) return result;
path.add(root.val); // 把根节点放进路径
traversal(root, sum - root.val);
return result;
}
} 14. 二叉搜索树的后序遍历反序列化
剑指offer 33
题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 1：
输入: [1,3,2,6,5]
输出: true
class Solution {
int[] post;
public boolean verifySequenceOfBST(int [] sequence) {
this.post = sequence;
return createBinerySearchTree(0 , post.length - 1);
}
public boolean createBinerySearchTree(int l , int r){
if(l >= r) return true;
int root = post[r]; // 获得根节点
int k = l;
while(k < r && post[k] < root) k ++; // 找到比根小的节点数，即为左子树节点的个数
for(int i = k;i < r;i ++){ // 如果右子树中节点中有小于根节点的 返回 false
if(post[i] < root) return false;
}
return createBinerySearchTree(l , k - 1) && createBinerySearchTree(k , r - 1);
}
} 15. 由先序和中序构建二叉树
剑指offer 7
题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
class Solution {
int[] preorder;
int[] inorder;
Map<Integer,Integer> map;
public TreeNode createTree(int pl , int pr , int ol , int or){
if(pl > pr) return null;
TreeNode root = new TreeNode(preorder[pl]);
int k = map.get(root.val);
root.left = createTree(pl + 1 , pl + k - ol , ol , k - 1);
root.right = createTree(pl + k - ol + 1 , pr , k + 1 , or);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
map = new HashMap<>();
for(int i = 0; i < inorder.length; i ++) map.put(inorder[i] , i);
return createTree(0 , preorder.length - 1 , 0 , inorder.length - 1);
}
} 16. 由中序和后续构建二叉树
力扣 106
题目描述：根据一棵树的中序遍历与后序遍历构造二叉树。你可以假设树中没有重复的元素。
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
class Solution {
int[] inorder;
int[] postorder;
Map<Integer , Integer> map;
public TreeNode createTree(int ol , int or , int pl , int pr){
if(ol > or) return null;
TreeNode root = new TreeNode(postorder[pr]);
int k = map.get(root.val);
root.left = createTree(ol , k - 1 , pl , pl + k - ol - 1);
root.right = createTree(k + 1 , or , pl + k - ol , pr - 1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
map = new HashMap<>();
for(int i = 0;i < inorder.length;i ++) map.put(inorder[i] , i);
return createTree(0 , inorder.length - 1 , 0 , postorder.length - 1);
}
} 17. 由前序和后续构建二叉树
力扣 889
题目描述：返回与给定的前序和后序遍历匹配的任何二叉树。
pre 和 post 遍历中的值是不同的正整数。
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
class Solution {
int[] pre;
int[] post;
Map<Integer , Integer> map;
public TreeNode createTree(int pre_l , int pre_r , int post_l , int post_r){
if(pre_l > pre_r) return null;
if(pre_l == pre_r) //要提前结束，不然后面 pre[pre_l + 1] 数组会越界，（注意105题、106题）
return new TreeNode(pre[pre_l]);
TreeNode root = new TreeNode(pre[pre_l]);
int k = map.get(pre[pre_l + 1]);
root.left = createTree(pre_l + 1 , pre_l + 1 + k - post_l , post_l , k);
root.right = createTree(pre_l + 1 + k - post_l + 1 , pre_r , k + 1 , post_r - 1);
return root;
}
public TreeNode constructFromPrePost(int[] pre, int[] post) {
this.pre = pre;
this.post = post;
map = new HashMap<>();
for(int i = 0 ; i < post.length ; i ++) map.put(post[i] , i);
return createTree(0 , pre.length - 1 , 0 , post.length - 1);
}
} 总结 15-17 ： 三种遍历两两结合，重构二叉树的过程，
只有在前后结合时，需要考虑一下边界溢出的问题(代码中已指出)
其他两种只需要正常考虑边界范围即可
18. 不同的二叉搜索树
力扣 96
题目描述：给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
G(n)函数的值在数学上被称为卡塔兰数 Cn。%7D%7Bn%20%2B%202%7D%20C_%7Bn%7D "图片标题")
class Solution {
public int numTrees(int n) {
// 提示：我们在这里需要用 long 类型防止计算过程中的溢出
long C = 1;
for (int i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int) C;
}
} 19. 二叉搜索树与双向链表
剑指offer 36
题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
class Solution {
Node head , pre = null;
public void inOrderDFS(Node root){
if(root == null) return ;
inOrderDFS(root.left);
if(pre == null){
head = root; //只进行一次赋值，即最终的头节点
} else {
pre.right = root;
root.left = pre;
}
pre = root;
inOrderDFS(root.right);
}
public Node treeToDoublyList(Node root) {
if(root == null) return root;
inOrderDFS(root);
head.left = pre;
pre.right = head;
return head;
}
} 20. 对称二叉树
剑指offer 36
题目描述：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null ? true : check(root.left , root.right);
}
public boolean check(TreeNode L , TreeNode R){
if(L == null && R == null) return true;
if(L == null || R == null || L.val != R.val) return false;
return check(L.left , R.right) && check(L.right , R.left);
}
} 21. 删除二叉搜索树中的节点
力扣 450
题目描述：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
分析： 删除的过程也分为几种情况
- 如果要删除的节点是叶子节点，我们直接删除即可。
- 如果删除的结点不是叶子节点，并且有一个子节点为空，我们直接返回另一个不为空的子节点即可。
- 如果删除的结点不是叶子节点，并且左右子树都不为空，我们可以用左子树的最大值替换掉要删除的节点或者用右子树的最小值替换掉要删除的节点都是可以的。
class Solution{
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null)
return null;
//通过递归的方式要先找到要删除的结点
if (key < root.val) {
//要删除的节点在左子树上
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
//要删除的节点在右子树上
root.right = deleteNode(root.right, key);
} else {
//找到了要删除的节点。
//如果左子树为空，我们只需要返回右子树即可
if (root.left == null)
return root.right;
//如果右子树为空，我们只需要返回左子树即可
if (root.right == null)
return root.left;
//说明两个子节点都不为空，我们可以找左子树的最大值，
//也可以找右子树的最小值替换
//这里是用右子树的最小值替换
//TreeNode minNode = findMin(root.right);
//root.val = minNode.val;
//root.right = deleteNode(root.right, root.val);
//这里是用左子树的最大值替换
TreeNode maxNode = findMax(root.left);
root.val = maxNode.val;
root.left = deleteNode(root.left, root.val);
}
return root;
}
// 找右子树的最小值
// private TreeNode findMin(TreeNode node) {
// while (node.left != null)
// node = node.left;
// return node;
// }
//找左子树的最大值
private TreeNode findMax(TreeNode node) {
while (node.right != null)
node = node.right;
return node;
}
} 补充：
- Successor 代表的是中序遍历序列的下一个节点。即比当前节点大的最小节点，简称后继节点。 先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，则最后指向的节点为后继节点。
- Predecessor 代表的是中序遍历序列的前一个节点。即比当前节点小的最大节点，简称前驱节点。先取当前节点的左节点，然后取该节点的右节点，直到右节点为空，则最后指向的节点为前驱节点。
public int successor(TreeNode root) {
root = root.right;
while (root.left != null) root = root.left;
return root;
}
public int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) root = root.right;
return root;
} 22. N叉树的深度
力扣 559
题目描述：给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
分析：思路很简单，和二叉树一样，不同点是每次递归求解每个根节点的所有孩子节点所在的子树的高度，然后获得一个最大值
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
};
*/
class Solution {
public int maxDepth(Node root) {
if(root == null) return 0;
if(root.children.size() == 0) return 1;
int len = root.children.size();
int maxDept = Integer.MIN_VALUE;
for(int i = 0 ; i < len ; i ++){
int dept = maxDepth(root.children.get(i));
maxDept = Math.max(maxDept , dept);
}
return maxDept + 1;
}
} 23. 合并二叉树
力扣 617
题目描述：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1 == null) return t2; // 如果t1为空，合并之后就应该是t2
if(t2 == null) return t1; // 如果t2为空，合并之后就应该是t1
// 修改 t1 的数值和结构
t1.val += t2.val;
t1.left = mergeTrees(t1.left , t2. left);
t1.right = mergeTrees(t1.right , t2.right);
return t1;
}
} 24. 二叉搜索树的插入操作
力扣 701
题目描述：给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
if(root.val > val) root.left = insertIntoBST(root.left , val);
if(root.val < val) root.right = insertIntoBST(root.right , val);
return root;
}
} 
拼多多集团-PDD公司氛围 517人发布
