年輕即出發(fā)...
簡(jiǎn)書：http://www.itdecent.cn/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源碼：https://github.com/zqtao2332
個(gè)人網(wǎng)站：http://www.zqtaotao.cn/ （停止維護(hù)更新內(nèi)容，轉(zhuǎn)移簡(jiǎn)書）
QQ交流群：606939954
? 咆哮怪獸一枚...嗷嗷嗷...趁你現(xiàn)在還有時(shí)間，盡你自己最大的努力。努力做成你最想做的那件事，成為你最想成為的那種人，過(guò)著你最想過(guò)的那種生活。也許我們始終都只是一個(gè)小人物，但這并不妨礙我們選擇用什么樣的方式活下去，這個(gè)世界永遠(yuǎn)比你想的要更精彩。
最后：喜歡編程，對(duì)生活充滿激情
本節(jié)內(nèi)容預(yù)告
實(shí)例1：二叉樹的先序、中序、后序遍歷，包括遞歸方式和非遞歸方式
實(shí)例2：如何直觀的打印一顆二叉樹
實(shí)例3：在二叉樹中找到一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)（前驅(qū)）
實(shí)例4：介紹二叉樹的序列化和反序列化
實(shí)例5：
實(shí)例6：平衡二叉樹
實(shí)例7：判斷一棵樹是否是搜索二叉樹、判斷一棵樹是否是完全二叉樹
實(shí)例8：已知一棵完全二叉樹，求其節(jié)點(diǎn)的個(gè)數(shù)
實(shí)例9：
實(shí)例10：
本節(jié)全部都是關(guān)于二叉樹的問(wèn)題。
實(shí)例1
實(shí)現(xiàn)二叉樹的先序、中序、后序遍歷，包括遞歸方式和非遞歸方式
遞歸方式遍歷二叉樹
其實(shí)三種遍歷都是一樣的，唯一的區(qū)別就是打印的時(shí)機(jī)不同
先打印就是先序
中間打印就是中序
后打印就是后序
非遞歸遍歷二叉樹
使用輔助棧根據(jù)不同的壓棧順序進(jìn)行遍歷。
import java.util.Stack;
/**
* @description: 二叉樹操作：前序遍歷二叉樹、中序、后序遍歷二叉樹。
* @version: 1.0
*/
public class Code_25_PreorderInorderPostorderTraversal {
// 二叉樹節(jié)點(diǎn)
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 前序遍歷遞歸版
public static void preOrderRecur(Node head) {
if (head == null)
return;
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
// 中序遍歷遞歸版
public static void inOrderRecur(Node head) {
if (head == null) return;
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}
// 后序遍歷遞歸版
public static void postOrderRecur(Node head) {
if (head == null) return;
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.value + " ");
}
/**
* 前序遍歷：非遞歸
* 1、準(zhǔn)備一個(gè)棧，先入頭結(jié)點(diǎn)
* 2、遍歷棧（循環(huán)條件：棧不為空）
* 從棧中彈出一個(gè)元素，打印
* 判斷這個(gè)節(jié)點(diǎn)是否有右子樹，有入棧
* 判斷這個(gè)節(jié)點(diǎn)是否有左子樹，有入棧
* @param head
*/
public static void preOrderUnRecur(Node head) {
System.out.print("pre-order: ");
if (head == null) return;
Stack<Node> stack = new Stack<>();
stack.add(head);
// stack.push(head); // 存頭結(jié)點(diǎn)
// stack 的add 方法和push 方法本質(zhì)上沒(méi)有區(qū)別，都是調(diào)用java.util.Vector.add(E)方法
// 唯一不同就是返回值不同，add 返回添加成功否，push 返回這個(gè)添加的元素對(duì)象
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
System.out.println();
}
/**
* 中序遍歷，非遞歸
*
* 全力壓左邊界入棧，整棵樹可以被左邊界分解
*
* 1、準(zhǔn)備一個(gè)棧
* 2、遍歷（循環(huán)條件：棧不為空 || 當(dāng)前節(jié)點(diǎn)不為空）
* a、當(dāng)前節(jié)點(diǎn)不為空，就將當(dāng)前節(jié)點(diǎn)入棧，指向左孩子
*
* b、當(dāng)前節(jié)點(diǎn)為空，棧不為空，從當(dāng)前棧中彈出一個(gè)節(jié)點(diǎn)，打印
* 當(dāng)前節(jié)點(diǎn) 指向當(dāng)前節(jié)點(diǎn)的右孩子
*
* 即：
* if（當(dāng)前節(jié)點(diǎn)不為空）{ //
* 壓入當(dāng)前節(jié)點(diǎn)的左孩子
* 當(dāng)前節(jié)點(diǎn) = 當(dāng)前節(jié)點(diǎn).left
* } else {
* 彈出一個(gè)節(jié)點(diǎn)， 打印
* 指向右孩子，繼續(xù)循環(huán) 2 過(guò)程
* }
* @param head
*/
public static void inOrderUnRecur(Node head){
System.out.print("in-order: ");
if (head == null) return;
Stack<Node> stack = new Stack<>();
while (head != null || !stack.isEmpty()){
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
System.out.println();
}
/**
* 后序遍歷：非遞歸
*
* 前序遍歷：中左右 非遞歸 思路
* 保存頭結(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)有右孩子，存
* 當(dāng)前節(jié)點(diǎn)有左孩子，存
* 總體入棧順序是：右左 ---> 打印結(jié)果：中左右
*
* 后序遍歷 ：左右中 思路：借用前序遍歷的思路，做出一個(gè) 中右左的打印結(jié)果，在該打印的時(shí)候入另一個(gè)棧
* 根據(jù)棧的彈出順序，就成了左右中
*
* 保存頭結(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)有左孩子，存
* 當(dāng)前節(jié)點(diǎn)有右孩子，存
* 總體入棧順序是：左右 ---> 打印結(jié)果：中右左（不打印，節(jié)點(diǎn)入另一個(gè)棧）
*
* 最后在統(tǒng)一打印另一個(gè)棧的節(jié)點(diǎn) --- 中右左 ----> 左右中
* @param head
*/
public static void postOrderUnRecur1(Node head) {
System.out.print("post-order-1: ");
if (head == null) return;
Stack<Node> preStack = new Stack<>();
Stack<Node> postStack = new Stack<>();
preStack.add(head);
while (!preStack.isEmpty()) {
head = preStack.pop();
postStack.push(head); // 在本該打印的時(shí)機(jī)，選擇存入到另一個(gè)棧
if (head.left != null) {
preStack.push(head.left);
}
if (head.right != null){
preStack.push(head.right);
}
}
while (!postStack.isEmpty()){
System.out.print(postStack.pop().value + " ");
}
System.out.println();
}
// 暫時(shí)不要求理解
public static void postOrderUnRecur2(Node h) {
System.out.print("pos-order: ");
if (h != null) {
Stack<Node> stack = new Stack<Node>();
stack.push(h);
Node c = null;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
h = c;
}
}
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
// recursive
System.out.println("==============recursive==============");
System.out.print("pre-order: ");
preOrderRecur(head);
System.out.println();
System.out.print("in-order: ");
inOrderRecur(head);
System.out.println();
System.out.print("pos-order: ");
postOrderRecur(head);
System.out.println();
// unrecursive
System.out.println("============unrecursive=============");
preOrderUnRecur(head);
inOrderUnRecur(head);
postOrderUnRecur1(head);
postOrderUnRecur2(head);
}
}
實(shí)例2
如何直觀的打印一顆二叉樹
左神設(shè)計(jì)的打印方式，雖然看著丑！但很實(shí)用
package cn.zqtao.learn.day4;
/**
* 直觀打印二叉樹
*/
public class Code_26_PrintBinaryTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(-222222222);
head.right = new Node(3);
head.left.left = new Node(Integer.MIN_VALUE);
head.right.left = new Node(55555555);
head.right.right = new Node(66);
head.left.left.right = new Node(777);
printTree(head);
head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.right.left = new Node(5);
head.right.right = new Node(6);
head.left.left.right = new Node(7);
printTree(head);
head = new Node(1);
head.left = new Node(1);
head.right = new Node(1);
head.left.left = new Node(1);
head.right.left = new Node(1);
head.right.right = new Node(1);
head.left.left.right = new Node(1);
printTree(head);
head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
printTree(head);
}
}
實(shí)例3
在二叉樹中找到一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)
【題目】 現(xiàn)在有一種新的二叉樹節(jié)點(diǎn)類型如下：
public class Node{
public int value;
public Node parent; // 父節(jié)點(diǎn)
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
該結(jié)構(gòu)比普通二叉樹節(jié)點(diǎn)結(jié)構(gòu)多了一個(gè)指向父節(jié)點(diǎn)的parent指針。
假 設(shè)有一 棵Node類型的節(jié)點(diǎn)組成的二叉樹，樹中每個(gè)節(jié)點(diǎn)的parent指針 都正確地指向 自己的父節(jié)點(diǎn)，頭節(jié)點(diǎn)的parent指向null。只給一個(gè)在 二叉樹中的某個(gè)節(jié)點(diǎn) node，請(qǐng)實(shí)現(xiàn)返回node的后繼節(jié)點(diǎn)的函數(shù)。
在二 叉樹的中序遍歷的序列中， node的下一個(gè)節(jié)點(diǎn)叫作node的后繼節(jié)點(diǎn)。
思路：
給定二叉樹中的任意一個(gè)節(jié)點(diǎn)，找到，當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)，并返回
第一種情況：如果node有右子樹，那么后繼節(jié)點(diǎn)就是整棵右子樹上最左邊的節(jié)點(diǎn) 右子樹--->最左
第二種情況：如果node沒(méi)有右子樹
a、node是不是node 父節(jié)點(diǎn)的左孩子, 是，返回父節(jié)點(diǎn)
b、不是，向上遍歷，創(chuàng)建指針parent指向node父節(jié)點(diǎn)，node節(jié)點(diǎn)和父節(jié)點(diǎn)一直上移，找到 a 的情況， 返回
PS: 代碼中給出了尋找前驅(qū)節(jié)點(diǎn)的思路
/**
* @auther: zqtao
* @description:
* @version: 1.0
*/
public class Code_27_SuccessorNode {
public static class Node{
public int value;
public Node parent; // 父節(jié)點(diǎn)
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
/**
* 給定二叉樹中的任意一個(gè)節(jié)點(diǎn)，找到，當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)，并返回
*
* 第一種情況：如果node有右子樹，那么后繼節(jié)點(diǎn)就是整棵右子樹上最左邊的節(jié)點(diǎn) 右子樹--->最左
* 第二種情況：如果node沒(méi)有右子樹
* a、node是不是node 父節(jié)點(diǎn)的左孩子, 是，返回父節(jié)點(diǎn)
* b、不是，向上遍歷，創(chuàng)建指針parent指向node父節(jié)點(diǎn)，node節(jié)點(diǎn)和父節(jié)點(diǎn)一直上移，找到 a 的情況， 返回
*
*/
public static Node successorNode(Node node){
if (node == null) return node;
if (node.right != null) { // 有右孩子
return getLeftMostOfNodeHaveRightChild(node.right);
} else { // 無(wú)右孩子
Node parent = node.parent;
while (parent != null && parent.left != node) { // parent != null 針對(duì)的是整個(gè)二叉樹上的最后一個(gè)節(jié)點(diǎn)
node = parent;
parent = parent.parent;
}
return parent;
}
}
/**
* 有右子樹找后繼節(jié)點(diǎn)
* @param node 目標(biāo)節(jié)點(diǎn)的右節(jié)點(diǎn)
* @return 后繼節(jié)點(diǎn)
*
* 思路，如果目標(biāo)節(jié)點(diǎn)有右子樹，那么后繼節(jié)點(diǎn)就是整棵右子樹上最左邊的那個(gè)節(jié)點(diǎn)
*/
public static Node getLeftMostOfNodeHaveRightChild(Node node){
if (node == null) return node;
while (node.left != null) {
node = node.left;
}
return node;
}
public static void main(String[] args) {
Node head = new Node(6);
head.parent = null;
head.left = new Node(3);
head.left.parent = head;
head.left.left = new Node(1);
head.left.left.parent = head.left;
head.left.left.right = new Node(2);
head.left.left.right.parent = head.left.left;
head.left.right = new Node(4);
head.left.right.parent = head.left;
head.left.right.right = new Node(5);
head.left.right.right.parent = head.left.right;
head.right = new Node(9);
head.right.parent = head;
head.right.left = new Node(8);
head.right.left.parent = head.right;
head.right.left.left = new Node(7);
head.right.left.left.parent = head.right.left;
head.right.right = new Node(10);
head.right.right.parent = head.right;
Node test = head.left.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left.left.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left.right.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right.left.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right.right; // 10's next is null
System.out.println(test.value + " next: " + successorNode(test));
}
/*
補(bǔ)充：二叉樹尋找前驅(qū)節(jié)點(diǎn)
回憶一下二叉樹尋找后繼節(jié)點(diǎn)
1、有右孩子
右孩子 ---> 最左
2、無(wú)右孩子
找其中父節(jié)點(diǎn)的【左子樹節(jié)點(diǎn)】等于當(dāng)前節(jié)點(diǎn)（一直在向上移動(dòng)，即，當(dāng)前節(jié)點(diǎn)在變）的父節(jié)點(diǎn)
同理前驅(qū)
1、有左孩子
左孩子 ---> 最右
2、無(wú)孩子
找其中父節(jié)點(diǎn)的【右子樹節(jié)點(diǎn)】等于當(dāng)前節(jié)點(diǎn)（一直在向上移動(dòng)，即，當(dāng)前節(jié)點(diǎn)在變）的父節(jié)點(diǎn)
*/
}
實(shí)例4
介紹二叉樹的序列化和反序列化
二叉樹被記錄成文件的過(guò)程叫做二叉樹的序列化
通過(guò)記錄的文件重建二叉樹的過(guò)程叫做二叉樹的反序列化。
方法：先序、中序、后序、按層遍歷都可以實(shí)現(xiàn)二叉樹的序列化和反序列化。
但是我悲哀的發(fā)現(xiàn)，學(xué)習(xí)完了左神的兩個(gè)序列化和反序列化方式后，我想繼續(xù)其他方式編寫，出現(xiàn)了bug, 向百度求助查找時(shí)，悲哀的發(fā)現(xiàn)都是一群水軍，只要你搜索二叉樹的序列化和反序列化，所有人的帖子都是驚人的雷同，說(shuō)的一句話就是左神在課堂上說(shuō)的：“先序，中序，后序序列化和反序列是類似的，這里以先序?yàn)槔?，，，然后，，，”，因?yàn)樽笊裰恢v了二叉樹的先序，給出了層次遍歷的方式，然后就爆炸了，所有的帖子都是先序?yàn)槔?，我瘋狂找網(wǎng)上中序的方式實(shí)現(xiàn)序列化，，，得到的答案是：呵呵
這讓菜雞的我很難受。只能先放棄，等以后有能力再加上吧，現(xiàn)在太菜了。
傷心的我，連左神的代碼都懶得改了
import java.util.LinkedList;
import java.util.Queue;
/**
* @description:
* @version: 1.0
*/
public class Code_28_SerializeAndReconstructTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// =================================== {先序} ============================================
// 通過(guò)先序遍歷來(lái)序列化二叉樹
public static String serialByPre(Node head) {
if (head == null) return "#!";
String res = head.value + "!";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
// 通過(guò)先序遍歷反序列化二叉樹
public static Node reconByPreString(String serialNodeString) {
return reconPreOrder(getQueue(serialNodeString));
}
public static Node reconPreOrder(Queue<String> queue) {
String poll = queue.poll();
if (poll.equals("#"))
return null;
// 不為空，消費(fèi)這個(gè)節(jié)點(diǎn)
Node head = new Node(Integer.parseInt(poll));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
public static Queue<String> getQueue(String serialNodeString) {
if (serialNodeString == null) return null;
String[] split = serialNodeString.split("!");
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < split.length; i++) {
queue.add(split[i]);
}
return queue;
}
// =================================== {中序} ============================================
// 中序遍歷序列化
public static String serialByIn(Node head) {
if (head == null) return "#!";
String res = serialByIn(head.left);
res += head.value + "!";
res += serialByIn(head.right);
return res;
}
public static Node reconByInString(String serialNodeString) {
return reconByIn(getQueue(serialNodeString));
}
// 中序遍歷反序列化: 不會(huì)
public static Node reconByIn(Queue<String> queue) {
return null;
}
public static String serialByLevel(Node head) {
if (head == null) {
return "#!";
}
String res = head.value + "!";
Queue<Node> queue = new LinkedList<Node>();
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
if (head.left != null) {
res += head.left.value + "!";
queue.offer(head.left);
} else {
res += "#!";
}
if (head.right != null) {
res += head.right.value + "!";
queue.offer(head.right);
} else {
res += "#!";
}
}
return res;
}
public static Node reconByLevelString(String levelStr) {
String[] values = levelStr.split("!");
int index = 0;
Node head = generateNodeByString(values[index++]);
Queue<Node> queue = new LinkedList<Node>();
if (head != null) {
queue.offer(head);
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNodeByString(values[index++]);
node.right = generateNodeByString(values[index++]);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return head;
}
public static Node generateNodeByString(String val) {
if (val.equals("#")) {
return null;
}
return new Node(Integer.valueOf(val));
}
// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
Node head = null;
printTree(head);
String pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
String level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(1);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.right.right = new Node(5);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(100);
head.left = new Node(21);
head.left.left = new Node(37);
head.right = new Node(-42);
head.right.left = new Node(0);
head.right.right = new Node(666);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
}
}
實(shí)例6
判斷一棵二叉樹是否是平衡二叉樹。平衡二叉樹的性質(zhì)為:要么是一棵空樹,要么任何一個(gè)節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值不超過(guò)1。給定一棵二叉樹的頭節(jié)點(diǎn)head,判斷這棵二叉樹是否為平衡二又樹。
遞歸函數(shù)套路，高度套路化（也叫樹形dp, 就是樹形動(dòng)態(tài)規(guī)劃）
? 1、分析各種可能性
? 2、設(shè)計(jì)返回結(jié)構(gòu)
分析好可能性后，確定要收集的信息，定義好返回結(jié)構(gòu)，
根據(jù)子過(guò)程收集的信息，自己在決策過(guò)程也加工整合出同樣結(jié)構(gòu)的信息，往上一層進(jìn)行返回。
這個(gè)套路最重要的是列出所有的可能性。
比如這道題：平衡二叉樹
可能性，考慮以每一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的每一棵子樹是否也是平衡的
? 1、左子樹是否平衡
? 2、右子樹是否平衡
? 3、左子樹是否平衡和高度
? 4、右子樹是否平衡和高度
當(dāng)前節(jié)點(diǎn)的高度是根據(jù)子樹給的高度決定的。
6_1_平衡二叉樹_任意一個(gè)節(jié)點(diǎn)返回信息.png
/**
* @description:
* @version: 1.0
*/
public class Code_29_IsBanlaceTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 遞歸返回值結(jié)構(gòu)
public static class ReturnData{
public boolean isB; // 是否平衡
public int heith; // 高度
public ReturnData(boolean isB, int heith) {
this.heith = heith;
this.isB = isB;
}
}
public static boolean isBanlanceTree(Node head){
return process(head).isB;
}
/**
* 遞歸處理過(guò)程
*
* 遞歸套路：分析好可能性后，確定要收集的信息，定義好返回結(jié)構(gòu)，
* 根據(jù)子過(guò)程收集的信息，自己在決策過(guò)程也加工整合出同樣結(jié)構(gòu)的信息，往上一層進(jìn)行返回。
*
*
* 這個(gè)套路最重要的是列出所有的可能性。
*
* 比如這道題：平衡二叉樹
* 可能性，考慮以每一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的每一棵子樹是否也是平衡的
*
* 1、左子樹是否平衡
*
* 2、右子樹是否平衡
*
* 3、左子樹是否平衡和高度
*
* 4、右子樹是否平衡和高度
*
*
*
* 當(dāng)前節(jié)點(diǎn)的高度是根據(jù)子樹給的高度決定的。
* @param head
* @return
*/
public static ReturnData process(Node head){
// 07
if (head == null) return new ReturnData(true, 0);// null是平衡樹
// 收集左子樹信息
ReturnData leftData = process(head.left);
if (!leftData.isB) { // 左子樹不平衡
return new ReturnData(false,0);
}
// 收集右子樹信息
ReturnData rightData = process(head.right);
if (!rightData.isB) { // 左子樹不平衡
return new ReturnData(false, 0);
}
// 根據(jù)左右子樹信息，加工整合出同樣結(jié)構(gòu)的信息
if (Math.abs(leftData.heith - rightData.heith) > 1) { // 左右子樹平衡，高度差大于1情況
return new ReturnData(false, 0);
}
// 平衡，往上一層進(jìn)行返回
return new ReturnData(true, Math.max(leftData.heith, rightData.heith) + 1);
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
System.out.println(isBanlanceTree(head));
}
}
實(shí)例7
判斷一棵樹是否是搜索二叉樹、判斷一棵樹是否是完全二叉樹
搜索二叉樹：任意節(jié)點(diǎn)的左節(jié)點(diǎn)都比自己小，右節(jié)點(diǎn)都比自己大
二叉樹中序遍歷的結(jié)果是依次升序的就是搜索二叉樹，否則就不是。注意：通常搜索二叉樹是不含重復(fù)值節(jié)點(diǎn)的。
完全二叉樹
判斷一棵二叉樹是否是完全二叉樹,依據(jù)以下標(biāo)準(zhǔn)會(huì)使判斷過(guò)程變得簡(jiǎn)單且易實(shí)現(xiàn):
1,按層遍歷二叉樹,從每層的左邊向右邊依次遍歷所有的節(jié)點(diǎn)。
2,如果當(dāng)前節(jié)點(diǎn)有右孩子,但沒(méi)有左孩子,直接返回false.
3,如果當(dāng)前節(jié)點(diǎn)并不是左右孩子全有,那之后的節(jié)點(diǎn)必須都為葉節(jié)點(diǎn),否則返回false.
4,遍歷過(guò)程中如果不返回false,遍歷結(jié)束后返回true.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* @description:
* @version: 1.0
*/
public class Code_30_IsBSTAndCBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 回憶之前學(xué)的非遞歸：中序遍歷
// 全力壓左孩子入棧，整棵二叉樹可以被分解為多個(gè)左子樹狀態(tài)
/*public static void inOrderUnRecure(Node head){
System.out.println("in-order: ");
if (head != null){
Stack<Node> stack = new Stack<>();
while (head != null || !stack.isEmpty()) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
}*/
// 根據(jù)非遞歸形式改寫中序遍歷，判斷搜索二叉樹
// 搜索二叉樹特點(diǎn)，中序遍歷結(jié)果是依次遞增的
public static boolean BST(Node head){
if (head == null){
return true;
}
int val = Integer.MIN_VALUE;
Stack<Node> stack = new Stack<>();
while (head != null || !stack.isEmpty()){
if (head != null) {
stack.add(head);
head = head.left;
} else {
head = stack.pop();
if (val > head.value){
return false;
} else {
val = head.value;
}
head = head.right;
}
}
return true;
}
// 層次遍歷進(jìn)行遍歷
/**
* 判斷一棵二叉樹是否是完全二叉樹,
* 依據(jù)以下標(biāo)準(zhǔn)會(huì)使判斷過(guò)程變得簡(jiǎn)單且易實(shí)現(xiàn):
*
* 1,按層遍歷二叉樹,從每層的左邊向右邊依次遍歷所有的節(jié)點(diǎn)。
* 2,如果當(dāng)前節(jié)點(diǎn)有右孩子,但沒(méi)有左孩子,直接返回false.
* 3,如果當(dāng)前節(jié)點(diǎn)并不是左右孩子全有,那之后的節(jié)點(diǎn)必須都為葉節(jié)點(diǎn),否則返回false.
* 4,遍歷過(guò)程中如果不返回false,遍歷結(jié)束后返回true.
*/
public static boolean CBT(Node head){
if (head == null) return true;
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
Node L = null;
Node R = null;
boolean leaf = false; // 記錄接下來(lái)的遍歷是否都是葉節(jié)點(diǎn)的遍歷
while (!queue.isEmpty()){
head = queue.poll();
L = head.left;
R = head.right;
// 排除掉不是的可能性方案
if (
(leaf && (L != null || R != null)) // 當(dāng)開啟葉節(jié)點(diǎn)遍歷時(shí)：葉節(jié)點(diǎn)存在子樹，則返回false
|| (L == null && R != null) // 或者當(dāng)前節(jié)點(diǎn)的左子樹為null，右子樹不為空，返回false
) {
return false;
}
// 繼續(xù)遍歷子樹
if (L != null) {
queue.offer(L);
}
if (R != null) {
queue.offer(R);
} else {
leaf = true; // 當(dāng)左子樹，或者右子樹等于null時(shí)，開啟葉節(jié)點(diǎn)遍歷
}
}
return true;
}
public static void main(String[] args) {
Node head = new Node(4);
head.left = new Node(2);
head.right = new Node(6);
head.left.left = new Node(1);
head.left.right = new Node(3);
head.right.left = new Node(5);
printTree(head);
System.out.println(BST(head));
System.out.println(CBT(head));
}
//////////////////////////////////for test s/////////////////////////////////////////
// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
//////////////////////////////////for test e/////////////////////////////////////////
}
實(shí)例8
已知一棵完全二叉樹，求其節(jié)點(diǎn)的個(gè)數(shù)
要求：時(shí)間復(fù)雜度低于O(N)，N為這棵樹的節(jié)點(diǎn)個(gè)數(shù)
思路：
1、如果head== null ，空樹，return0
2、head ！= null，遍歷求樹的高度。遍歷左邊界即可。
3、遞歸過(guò)程：給定一個(gè)節(jié)點(diǎn)，返回以該節(jié)點(diǎn)為二叉樹的所有節(jié)點(diǎn)數(shù)
? 每一層只需要選擇一個(gè)節(jié)點(diǎn)node進(jìn)行遍歷過(guò)程
節(jié)點(diǎn)右子樹左邊界到達(dá)最后一層
證明該節(jié)點(diǎn)的左子樹是一課滿完全二叉樹
總節(jié)點(diǎn)=公式計(jì)算左子樹總節(jié)點(diǎn)數(shù) + 右子樹遞歸查找節(jié)點(diǎn)數(shù) + 當(dāng)前節(jié)點(diǎn)
8_1_節(jié)點(diǎn)右子樹左邊界到達(dá)最后一層.png
節(jié)點(diǎn)右子樹左邊界沒(méi)有到達(dá)最后一層
否， 證明該節(jié)點(diǎn)的右子樹是一課滿完全二叉樹
總節(jié)點(diǎn)=左子樹遞歸查找節(jié)點(diǎn)數(shù) + 公式計(jì)算右子樹總節(jié)點(diǎn)數(shù) + 當(dāng)前節(jié)點(diǎn)
8_2_節(jié)點(diǎn)右子樹左邊界沒(méi)有到達(dá)最后一層.png
因?yàn)槊恳粚佣贾贿x取了開一個(gè)節(jié)點(diǎn)進(jìn)行遞歸過(guò)程，所以真正訪問(wèn)節(jié)點(diǎn)的個(gè)數(shù)等于完全二叉樹的層數(shù)，都會(huì)查看node右子樹的最左節(jié)點(diǎn)，假設(shè)h層，會(huì)遍歷O(h)個(gè)節(jié)點(diǎn)，整個(gè)過(guò)程時(shí)間復(fù)雜度O(h^2)。也可以按照樣本量寫為O(logN ^2)
/**
* @description: 已知一棵完全二叉樹，求其節(jié)點(diǎn)的個(gè)數(shù)
*
*要求：時(shí)間復(fù)雜度低于O(N)，N為這棵樹的節(jié)點(diǎn)個(gè)數(shù)
*
* 時(shí)間復(fù)雜度 O(logN ^ 2)
* @version: 1.0
*/
public class Code_31_CompleteTreeNodeNumber {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static int getNumber(Node head) {
if (head == null) return 0;
return process(head, 1, getMaxLeftLevel(head, 1));
}
// 返回當(dāng)前節(jié)點(diǎn)為樹的節(jié)點(diǎn)數(shù)
public static int process(Node node, int level, int treeHigh) {
if (level == treeHigh) { // 當(dāng)前節(jié)點(diǎn)所在的層級(jí)是二叉樹的總高度，葉子節(jié)點(diǎn)
return 1;
}
if (getMaxLeftLevel(node.right, level + 1) == treeHigh) { // 該節(jié)點(diǎn)的右子樹的左邊界是否等于二叉樹總高度
// 是 ，證明該節(jié)點(diǎn)的左子樹是一課滿完全二叉樹
// 總節(jié)點(diǎn)=公式計(jì)算左子樹總節(jié)點(diǎn)數(shù) + 右子樹遞歸查找節(jié)點(diǎn)數(shù) + 當(dāng)前節(jié)點(diǎn)
return (1 << (treeHigh - level)) + process(node.right, level + 1, treeHigh);
/*
return (1<< (treeHigh - level) - 1) + process(node.right, level + 1, treeHigh) + 1;
*/
} else {
// 否， 證明該節(jié)點(diǎn)的右子樹是一課滿完全二叉樹
// 總節(jié)點(diǎn)=左子樹遞歸查找節(jié)點(diǎn)數(shù) + 公式計(jì)算右子樹總節(jié)點(diǎn)數(shù) + 當(dāng)前節(jié)點(diǎn)
return process(node.left, level + 1, treeHigh) + (1 << (treeHigh - level - 1));
}
}
// 返回當(dāng)前節(jié)點(diǎn)的最大左邊界
public static int getMaxLeftLevel(Node node, int level) {
while (node != null) {
level++;
node = node.left;
}
return level - 1;
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
System.out.println(getNumber(head));
}
}
