【算法自由之路】二叉樹的遞歸套路
預熱，二叉樹的後繼節點
話不多說，首先是一道練手題，尋找二叉樹任意給定節點的後繼節點，此二叉樹具備一個指向父節點的指針。
後繼節點：在中序周遊中于給定節點後一個列印的節點
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
public TreeNode(int val) {
this.val = val;
}
}
這道題其實主要考驗的是分類讨論和找規律的能力。首先了解中序周遊對每個子樹列印順序都是 左 中 右。比如下圖這個樹
做分類讨論其實就兩個情況：
- 該節點有右節點：後繼為右節點的最左節點
- 該節點沒有右節點：後繼節點為向上找，第一次子節點是父節點的左孩子的父節點，比如 8 的後繼就是 4
對于情況 2 我們其實可以反推來了解， 4 節點的前驅節點應該是 左子樹的最右的一個節點。
package algorithmic.base.tree;
/**
* @program: algorithmic-total-solution
* @description: 查找二叉樹的後繼節點，
* @author: wangzibin
* @create: 2023-01-10
**/
public class FindNextNode {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
public TreeNode(int val) {
this.val = val;
}
@Override
public String toString() {
return "TreeNode{" +
"val=" + val +
'}';
}
}
public static void print(TreeNode node) {
if (node == null) {
return;
}
print(node.left);
System.out.print(node.val);
print(node.right);
}
public static TreeNode findNextNode(TreeNode node) {
if (node == null) {
return null;
}
TreeNode result = null;
// 如果有右孩子，後繼節點是右孩子的最左節點
if (node.right != null) {
result = node.right;
while (result.left != null) {
result = result.left;
}
return result;
}
// 如果沒有右孩子,向上找第一個子孩子是左節點的父節點 （有點繞，看代碼）
result = node.parent;
// 注意最右節點沒有後繼節點
while (node.parent != null && node != result.left) {
node = node.parent;
result = node.parent;
}
return result;
}
public static void main(String[] args) {
TreeNode head = new TreeNode(2);
TreeNode node1 = new TreeNode(1);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
head.left = node1;
node1.parent = head;
head.right = node3;
node3.parent = head;
node3.right = node4;
node4.parent = node3;
node4.left = node5;
node5.parent = node4;
node4.right = node6;
node6.parent = node4;
node5.right = node7;
node7.parent = node5;
node7.right = node8;
node8.parent = node7;
print(head);
System.out.println();
System.out.println(findNextNode(node1));
System.out.println(findNextNode(head));
System.out.println(findNextNode(node3));
System.out.println(findNextNode(node5));
System.out.println(findNextNode(node7));
System.out.println(findNextNode(node8));
System.out.println(findNextNode(node4));
System.out.println(findNextNode(node6));
}
}
遞歸套路
二叉樹的遞歸套路有點像拆分子任務，将要求的最終結果分給每個分支去做
在實際應用中，對于一個整個樹的問題，假設可以向左右子樹要任何資訊，整合資訊後得出最終結果
整個拆分任務的操作我們交給了堆棧去做
遞歸套路 1 判斷一個二叉樹是平衡二叉樹
平衡二叉樹定義：對于樹中任意一個節點，其左子樹和右子樹的高度差不超過 1。
這裡假設我可以向左右子樹擷取任何資訊，那對于判斷我是否是平衡二叉樹的關系資訊是：
- 子樹高度
- 子樹是否是平衡二叉樹
于是我可以定義這樣一個傳回結構
public static class NodeInfo {
public boolean isBalanced;
public int high;
public NodeInfo(boolean isBalanced, int high) {
this.isBalanced = isBalanced;
this.high = high;
}
}
最終代碼很簡單
public class BalanceTree {
public static 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 static class NodeInfo {
public boolean isBalanced;
public int high;
public NodeInfo(boolean isBalanced, int high) {
this.isBalanced = isBalanced;
this.high = high;
}
}
public boolean isBalanced(TreeNode root) {
return getNodeInfo(root).isBalanced;
}
public NodeInfo getNodeInfo(TreeNode node) {
if (node == null) {
return new NodeInfo(true, 0);
}
// 擷取左子樹資訊
NodeInfo left = getNodeInfo(node.left);
// 擷取右子樹資訊
NodeInfo right = getNodeInfo(node.right);
// 如果左右子樹都平衡且高度差為 1 則我也平衡
boolean isBalanced = left.isBalanced && right.isBalanced && Math.abs(left.high - right.high) <= 1;
// 我的高度為左右子樹最大高度 +1
int high = Math.max(left.high, right.high) + 1;
return new NodeInfo(isBalanced, high);
}
}
可以直接到 leetcode 驗證 平衡二叉樹
感受到二叉樹的遞歸套路的魅力了嗎？關鍵點在于：
- 思考 目前 節點 與 左右子節點的關系 （一般的我們可以以 以 與目前節點有關 和 與目前節點無關 來進行分類讨論 ）
- 向左右子節點擷取什麼資訊能夠計算出我的資訊
- 整合資訊，定義結構
遞歸套路 2 計算給定樹結構中二叉搜尋子樹的最大鍵和值
首先定義二叉搜尋數 ： 對于樹中任意一個節點，其左樹都小于該節點，右樹都大于該節點
需要向左右節點要的資訊：
- 樹的最大值
- 樹的最小值
- 是否是二叉搜尋樹
- 目前樹的鍵和值
- 二叉搜尋子樹的最大鍵和值
在遞歸中就需要讨論最終結果是否與目前節點有關了，直接看代碼
package algorithmic.base.tree;
import javax.xml.soap.Node;
/**
* @program: algorithmic-total-solution
* @description: 二叉搜尋子樹最大鍵和值 https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/
* @author: wangzibin
* @create: 2023-01-11
**/
public class MaxSumBST {
public static 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 static class NodeInfo {
// 目前節點子樹最大值
private int max;
private int min;
private boolean isBst;
private int bstSum;
private int bstMaxSum;
@Override
public String toString() {
return "NodeInfo{" +
"max=" + max +
", min=" + min +
", isBst=" + isBst +
", bstSum=" + bstSum +
", bstMaxSum=" + bstMaxSum +
'}';
}
}
public static NodeInfo getInfo(TreeNode node) {
if (node == null) {
NodeInfo empty = new NodeInfo();
empty.isBst = true;
empty.min = Integer.MAX_VALUE;
empty.max = Integer.MIN_VALUE;
return empty;
}
NodeInfo leftInfo = getInfo(node.left);
NodeInfo rightInfo = getInfo(node.right);
NodeInfo current = new NodeInfo();
current.max = max(node.val, leftInfo.max, rightInfo.max);
current.min = min(node.val, leftInfo.min, rightInfo.min);
// 判斷是否與我有關, 當且僅當我也是二叉搜尋樹時最大值才與我有關，否則隻需要比較子樹值即可
if (leftInfo.isBst && rightInfo.isBst && leftInfo.max < node.val && rightInfo.min > node.val) {
// 左右子樹都是搜尋樹，且 左子樹最大值 小于 目前節點值 ，右子樹最小值 大于 目前節點值，則可讨論與目前節點有關的情況
current.isBst = true;
current.bstSum = node.val + leftInfo.bstSum + rightInfo.bstSum;
current.bstMaxSum = max(current.bstSum, leftInfo.bstMaxSum, rightInfo.bstMaxSum);
} else {
current.isBst = false;
current.bstMaxSum = Math.max(leftInfo.bstMaxSum, rightInfo.bstMaxSum);
}
return current;
}
public static int max(int num1, int num2, int num3) {
return Math.max(Math.max(num1, num2), num3);
}
public static int min(int num1, int num2, int num3) {
return Math.min(Math.min(num1, num2), num3);
}
public static int maxSumBST(TreeNode root) {
if (root == null) {
return 0;
}
int bstMaxSum = getInfo(root).bstMaxSum;
return Math.max(bstMaxSum, 0);
}
public static void main(String[] args) {
TreeNode treeNode1 = new TreeNode(1);
treeNode1.left = null;
TreeNode treeNode10 = new TreeNode(10);
TreeNode treeNode5 = new TreeNode(-5);
TreeNode treeNode20 = new TreeNode(20);
treeNode1.right = treeNode10;
treeNode10.left = treeNode5;
treeNode10.right = treeNode20;
System.out.println(maxSumBST(treeNode1));
}
}
驗證正确性 1373. 二叉搜尋子樹的最大鍵值和
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)