——總結(jié)左神進階班第四甜滨、五課有關樹的一些問題匯總
目錄：
- 判斷一顆樹是否是平衡二叉樹
- 尋找最大二叉搜索樹（節(jié)點個數(shù)和頭節(jié)點）
- 尋找一個樹中最大值和最小值（節(jié)點和值）
- 求一顆二叉樹上面的最遠距離
- 員工活躍度問題
判斷一顆樹是否是平衡二叉樹
基本思路：
-
首先獲取所需信息：
- 當前樹的左子樹是否是平衡二叉樹
- 當前樹的右子樹是否是平衡二叉樹
- 當前樹的左子樹的高度
- 當前樹的右子樹的高度
-
整合所用信息
- 如果左右子樹有一個不是平衡二叉樹，那么當前的樹肯定也不是平衡二叉樹如蚜。
- 如果左右子樹都是平衡二叉樹恐锣，且左右子樹的高度差不超過1夹囚，那么是平衡樹隙咸，否則不是平衡二叉樹沐悦。
代碼如下：
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 創(chuàng)建對象信息集
static class State{
boolean isAvl; // 當前樹是否是平衡二叉樹
int h; // 當前樹的高度
// 構(gòu)造器
public State(boolean isAvl, int h) {
this.isAvl = isAvl;
this.h = h;
}
}
// 判斷一顆樹是否是平衡二叉樹
public static boolean isAvl(TreeNode root){
return getAns(root).isAvl;
}
private static State getAns(TreeNode root) {
if(root == null) return new State(true,0);
// 獲取左右子樹的各自信息
State l = getAns(root.left);
State r = getAns(root.right);
// case——true;
if(!l.isAvl || !r.isAvl || Math.abs(l.h - r.h) > 1){
return new State(false,0);
}
// case——false
return new State(true,Math.max(l.h,r.h) + 1);
}
尋找最大二叉搜索樹（節(jié)點個數(shù)和頭節(jié)點）
LintCode910 | 尋找最大二叉搜索子樹 —— 需要會員
題目描述：
給定一顆二叉樹的頭節(jié)點head，請返回最大搜索二叉子樹的大小五督。
基本思路：
- 首先搜索所用信息：
- 左、右子樹中最大搜索二叉樹的頭節(jié)點瓶殃。
- 左充包、右子樹中最大二叉搜索子樹的節(jié)點個數(shù)。
- 左遥椿、右子樹中的最小節(jié)點值
- 左基矮、右子樹中的最大節(jié)點值
- 進行所用信息的整合
- case1 : 如果當前左右兩顆樹可以整合為一顆二叉搜索樹。
- case2 : 如果當前左右子樹無法整為一顆二叉搜索樹冠场，從左右子樹中挑選一顆較大搜索二叉樹家浇。
代碼如下：
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 創(chuàng)建對象信息集
static class State{
TreeNode head;
int size;
int min;
int max;
public State(TreeNode head, int size, int min, int max) {
this.head = head;
this.size = size;
this.min = min;
this.max = max;
}
}
// 返回最大的二叉搜索子樹的頭節(jié)點
public static TreeNode getMaxBST(TreeNode root){
return getAns(root).head;
}
private static State getAns(TreeNode root) {
if(root == null) return new State(null,0,Integer.MAX_VALUE,Integer.MIN_VALUE);
// 獲取左右子樹的信息
State l = getAns(root.left);
State r = getAns(root.right);
// case1: 左右子樹可以整合成一顆二叉搜索樹
int union = 0;
if(l.head == root.left && r.head == root.right && root.val > l.max && root.val < r .min){
union = l.size + r.size + 1;
}
// case2、3
int p1 = l.size;
int p2 = r.size;
int maxSize = Math.max(Math.max(p1,p2),union);
TreeNode maxHead = p1 > p2 ? l.head : r.head;
if(maxSize == union){
maxHead = root;
}
return new State(maxHead,maxSize,
Math.min(Math.min(l.min,r.min),root.val),Math.max(Math.max(l.max,r.max),root.val));
}
尋找一個樹中最大值和最小值（節(jié)點和值）
基本思路：
- 首先進行信息獲取
- 需要左子樹和右子樹各自的最小值
- 左子樹和右子樹各自的最大值
- 整合信息碴裙；
- 小值為左子樹的最小值钢悲、右子樹的最小值，以及當前root的值的最小值舔株。
- 樹的最大值為左子樹的最大值莺琳、右子樹的最大值，以及當前root的值的最大值载慈。
代碼如下：
// 創(chuàng)建對象信息集
static class State{
int min;
int max;
public State(int min, int max) {
this.min = min;
this.max = max;
}
}
// 返回二叉樹中的最大值和最小值
public static int[] getTreeBorderValue(TreeNode root){
State res = getAns(root);
return new int[]{res.min,res.max};
}
private static State getAns(TreeNode root) {
if(root == null) return new State(Integer.MAX_VALUE, Integer.MIN_VALUE);
// 獲取左右子樹的信息
State l = getAns(root.left);
State r = getAns(root.right);
// 整合信息
return new State(Math.min(Math.max(l.min,r.min),root.val),Math.max(Math.max(l.max,r.max),root.val));
}
public static void main(String[] args) {
TreeNode head1 = new TreeNode(1);
head1.left = new TreeNode(2);
head1.right = new TreeNode(3);
head1.left.left = new TreeNode(4);
head1.left.right = new TreeNode(5);
head1.right.left = new TreeNode(6);
head1.right.right = new TreeNode(7);
head1.left.left.left = new TreeNode(8);
head1.right.left.right = new TreeNode(9);
int[] arr1 = getTreeBorderValue(head1);
System.out.println(Arrays.toString(arr1));
TreeNode head2 = new TreeNode(1);
head2.left = new TreeNode(2);
head2.right = new TreeNode(3);
head2.right.left = new TreeNode(4);
head2.right.right = new TreeNode(5);
head2.right.left.left = new TreeNode(6);
head2.right.right.right = new TreeNode(7);
head2.right.left.left.left = new TreeNode(8);
head2.right.right.right.right = new TreeNode(9);
int[] arr2 = getTreeBorderValue(head2);
System.out.println(Arrays.toString(arr2));
}
求一顆二叉樹上面的最遠距離
題目描述：
在二叉樹中惭等，一個節(jié)點可以往上走也可以往下走，那么節(jié)點A總能走到節(jié)點B办铡。
節(jié)點A走到節(jié)點B的距離為：A走到B最短路徑上的節(jié)點個數(shù)辞做。
求一顆二叉樹上的最遠距離。
基本思路：
- 首先獲取有用的信息：
- 左右子樹上的最遠距離
- 左右子樹各自的高度
- 整合相關的有用信息：
- 當前樹中的最長距離為左子樹的最長距離寡具，右子樹的最長距離以及當前左子樹高度加上右子樹高度加1中取最大秤茅。
代碼如下：
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 創(chuàng)建對象信息集
static class State{
int maxLen; // 當前樹的最大距離
int height; // 當前樹的高度
State(int maxLen, int height) {
this.maxLen = maxLen;
this.height = height;
}
}
// 返回二叉樹中的最大值和最小值
public static int getMaxLength(TreeNode root){
return getAns(root).maxLen;
}
private static State getAns(TreeNode root) {
if(root == null) return new State(0, 0);
// 獲取左右子樹的信息
State l = getAns(root.left);
State r = getAns(root.right);
// 整合信息
return new State(Math.max(Math.max(l.maxLen,r.maxLen),(l.height + r.height + 1)),
Math.max(l.height,r.height) + 1);
}
員工活躍度問題
問題描述：
員工活躍度
基本思路：
- 對于任何一個員工，都有兩種可能性晒杈。情況一是該員工來的活躍度嫂伞，情況二是該員工不來的活躍度。
- 那么結(jié)果只需要返回root員工，也就是大boos（上級是他自己）的來和不來兩種情況下最大活躍度
- 如果大boss來帖努， 那么當前結(jié)果為boss的活躍度 加上所有boos直系子員工不來的活躍度撰豺。
- 如果大boss不來，那么當前結(jié)果就是boss直系子員工來或不來活躍度的自大值拼余。
- 最終比較來或者不來的活躍度污桦，取最大值。
如果給出的matirx是以樹結(jié)構(gòu)呈現(xiàn),則代碼如下：
static class Node {
int huo; // 員工活躍度
List<Node> subNodes; // 下屬員工活躍度集合
public Node(int huo){
this.huo = huo;
subNodes = new LinkedList<>();
}
}
// 創(chuàng)建對象信息集
static class State{
int lai_huo; // 當前員工來的活躍度
int bu_lai_huo; // 當前員工不來的活躍度
public State(int lai_huo, int bu_lai_huo) {
this.lai_huo = lai_huo;
this.bu_lai_huo = bu_lai_huo;
}
}
// 返回二叉樹中的最大值和最小值
public static int getMaxHappy(Node root){
State boss = getAns(root);
return Math.max(boss.bu_lai_huo,boss.lai_huo);
}
private static State getAns(Node root) {
int lai_huo = root.huo;
int bu_lai_hup = 0;
for (int i = 0; i < root.subNodes.size(); i++) {
Node empty = root.subNodes.get(i);
State cur = getAns(empty);
lai_huo += cur.bu_lai_huo;
bu_lai_hup += Math.max(cur.lai_huo,cur.bu_lai_huo);
}
return new State(lai_huo,bu_lai_hup);
}
如果給出的是二維數(shù)組的結(jié)構(gòu)匙监，則用動態(tài)規(guī)劃的思想取求解凡橱，代碼如下：
// 獲取最大的活躍值
public static int getMaxHappy(int[][] matrix){
// 創(chuàng)建一個二維數(shù)組存儲活躍度信息
int[][] dp = new int[matrix.length][2];
// 第一個元素表示該員工來的活躍度，第二個元素表示員工不來的活躍度
boolean[] visited = new boolean[matrix.length]; // 創(chuàng)建數(shù)組亭姥，表示當前員工是否已經(jīng)訪問過
// 遍歷martix稼钩，找出大boss的位置
int boss = 0;
for (int i = 0; i < matrix.length; i++) {
if(i == matrix[i][0]){
boss = i;
break;
}
}
// 進入遞歸返回最大
process(matrix,dp,visited,boss);
return Math.max(dp[boss][0],dp[boss][1]);
}
private static void process(int[][] matrix, int[][] dp, boolean[] visited, int boss) {
visited[boss] = true; // 計算boss的信息
dp[boss][0] = matrix[boss][1]; // 賦值活躍度
for (int i = 0; i < matrix.length; i++) {
if(matrix[i][0] == boss && !visited[boss]){
process(matrix, dp, visited, i);
dp[boss][0] += dp[i][1];
dp[boss][1] += Math.max(dp[i][0],dp[i][1]);
}
}
}
