考试重点，二叉树
1. 树的基本结构和定义
节点的定义，每个节点有val，和左右孩子:
public static class Node {
int value;
Node left;
Node right;
public Node(int data){
this.value = data;
}
} - 满二叉树(full binary tree), 除叶子结点外所有的节点都有两个子结点。
- 完全二叉树(complete binary tree), 满树或依次正在变成满树。
- 树的最大深度, 从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
2. 树的广度优先遍历-递归
在递归函数中，树的递归有它的递归序，在递归序列中第几次打印自己就对应着不同的递归顺序。
1.先序遍历<root> <left> <right>
第一次来到这个节点就打印，说明先遍历了根节点。
// 1. 先序遍历
public static void preOrder(Node head){
if(head == null){
return;
}
System.out.print(head.value + " ");
preOrder(head.left);
preOrder(head.right);
}
2.中序遍历<left> <root> <right>
第二次来到这个节点就打印，说明我的左子树已经打印完毕了。
特别用法: 中序遍历可以依次顺序的打印出，搜索二叉树上面的数据。
// 2. 中序遍历
public static void inOrder(Node head){
if(head == null){
return;
}
inOrder(head.left);
System.out.print(head.value + " ");
inOrder(head.right);
}3.后序遍历<left> <right> <root>
第三次来到这个节点就打印，说明我的左右子树都已经打印完毕了。
特别用法: 后序遍历可以依次删除节点，用在c++中析构整棵树。
// 3. 后序遍历
public static void postOrder(Node head){
if(head == null){
return;
}
postOrder(head.left);
postOrder(head.right);
System.out.print(head.value + " ");
}3. 树的宽度优先遍历-LevelOrder
树的层次遍历，可以逐层的遍历所有的节点。借助数据结构: 队列的先进先出，先压入头节点，每次弹出队首，再检查弹出节点的左右孩子，如果有则压入，直到队列为空。
public static void levelOrder(Node head) {
if (head==null) {
return;
}
Queue<Node> queue = new LinkedList<Node>();
//先压入头节点，初始化
queue.offer(head);
while(!queue.isEmpty()){
//每次弹出一个节点
head = queue.poll();
System.out.print(head.value + " ");
// 再入队它的左右孩子
if(head.left!=null){
queue.offer(head.left);
}
if(head.right!=null){
queue.offer(head.right);
}
}
System.out.println();
} 4. 递归模版
总结：
首先是考虑base case，叶子结点的返回情况，也就是当(node==null)时；然后接收左右子树返回的信息，整理出我需要的信息，把这些信息的返回值在左树和右树上求并集，对于所有的递归节点都一视同仁。
4.1 求高度
解法一: 递归方法
二叉树的高度定义为，从根节点到某个叶子节点的最长路径。这个问题可以用递归分解成，从叶子节点起，求每个以它为头节点的树的高度，逐次向上返回，每次判断左右子树的高度，取大值。
这里注意，在base case 时返回的是-1还是0，根据题目要求。
需要返回: 左右子树的高度leftHeight 和 rightHeight
整合信息: max(leftHeight, rightHeight) + 1
/*
@ 题目：求二叉树的高度
@ 解法：采用分治的思想，求左树的高度，再求右树的高度，最后根节点的高度就是
Max(leftsubtree.height, rightsubtree.height) + 1
@ base case: 当head为空时，就是叶子结点的左右树，此时返回-1，这样叶子结点的高度才是0
*/
public static int treeHeight(Node head){
if (head == null){
return -1;
}
int leftHeight = treeHeight(head.left);
int rightHeight = treeHeight(head.right);
return Math.max(leftHeight, rightHeight) + 1;
} 方法二: 非递归方法，层次遍历求最后一层
层次遍历，返回最后一个节点的level就是树的高度
public int maxDepth(TreeNode root) {
// 层次遍历
if(root==null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
HashMap<TreeNode, Integer> levelMap = new HashMap<TreeNode, Integer>();
queue.offer(root);
levelMap.put(root, 1);
TreeNode node = root;
while(!queue.isEmpty()){
node = queue.poll();
int curLevel = levelMap.get(node);
if(node.left!=null){
queue.offer(node.left);
levelMap.put(node.left, curLevel+1);
}
if(node.right!=null){
queue.offer(node.right);
levelMap.put(node.right, curLevel+1);
}
}
return levelMap.get(node);
} 4.2 验证平衡二叉树
定义:
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
解法:
需要的信息:1.左树是平衡的；2.右树是平衡的 3.左右树的高度差不超过一
需要构造一个返回类，里面有 是否平衡 和 树的高度 两个信息
base case: if root==null 则 返回 new ReturnData(true, 0)，表示空节点高度为0，且平衡
合并信息:isBalanced = leftData.isBalanced && rightData.isBalanced && 高度差小于2height = max(左高度，右高度) + 1
时间复杂度 O(N)
空间复杂度 O(N)
// 定义递归返回信息类型
public static class ReturnData {
boolean isBT;
int height;
ReturnData(boolean isBT, int height){
this.isBT = isBT;
this.height = height;
}
// 递归本体
public static ReturnData isBalanced_process(Node root) {
if(root==null){
return new ReturnData(true, 0);
}
// 从左右返回信息
ReturnData leftData = isBalanced_process(root.left);
ReturnData rightData = isBalanced_process(root.right);
// 整合信息:左树平衡，右树平衡，且高度差不超过一
int height = Math.max(leftData.height, rightData.height) + 1;
boolean isBT = leftData.isBT && rightData.isBT && (Math.abs(leftData.height - rightData.height)<2);
return new ReturnData(isBT, height);
}
} 4.3 验证搜索树
二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
解法一: 递归
分析可知，需要满足如下条件
- 左子树整体是 搜索树
- 右子树整体是 搜索树
- 左子树的max < x < 右子树的min
返回的信息类需要包含, 左树的max，右树的min，本身的isBST
base case: 如果为空，则返回 null ，在整合信息时处理null的情况
整合信息:
如果左不为空max = Max(max, leftData.max)min = Min(min, leftData.min)
如果右不为空max = Max(max, rightData.max)min = Min(min, rightData.min)
逻辑整合，要区分非空情况:
为空时，返回true，因为叶子节点的左右空节点不影响逻辑判断left_isBST = leftData!=null ? (leftData.isBST && leftData.max <= head.value) : true;right_isBST = rightData!=null ? (rightData.isBST && rightData.min > head.value) : true;isBST = left_isBST && right_isBST;
时间复杂度 O(N)
空间复杂度 O(N)
// 返回的信息类
ReturnData(boolean is, int min, int max){
this.isBST = is;
this.min = min;
this.max = max;
}
}
public static ReturnData recursiveProcess(Node head) {
// base case
if(head==null){
return null;
}
// 接受左右返回信息
ReturnData leftData = recursiveProcess(head.left);
ReturnData rightData = recursiveProcess(head.right);
// 整合信息: 整合min和max, 若左右子树为空，当前节点的min和max都是node节点自身无需比较
int min = head.value;
int max = head.value;
// 若左右子树不为空，更新
// 节点的左子树只包含小于当前节点的数。
// 节点的右子树只包含大于当前节点的数。
if(leftData!=null){
max = Math.max(max, leftData.max);
min = Math.min(min, leftData.min);
}
if(rightData!=null){
max = Math.max(max, rightData.max);
min = Math.min(min, rightData.min);
}
// 整合isBST
boolean isBST = false;
// 左树和node达标：左子树整体是BST 且 左树的max小于node
boolean condition_1 = leftData!=null ? (leftData.isBST && leftData.max <= head.value) : true;
// 右树和node达标：右子树整体是BST 且 右树的min大于node
boolean condition_2 = rightData!=null ? (rightData.isBST && rightData.min > head.value) : true;
if(condition_1 && condition_2){
isBST = true;
}
return new ReturnData(isBST, min, max);
} 解法二: 中序遍历, 验证输出序列是否是升序
// 用非递归的中序遍历整颗树，判断是否是升序
public static boolean isBST_inOrder(Node head) {
if (head==null){
return true;
}
Stack<Node> stack = new Stack<>();
Node node = head;
double pre = Double.MIN_VALUE;
while(!stack.isEmpty() || node!=null){
// 左遍历
if(node!=null){
stack.push(node);
node = node.left;
}
// 退出左遍历，先弹出一个节点，在对右节点执行左遍历
else{
node = stack.pop();
// 验证升序，一旦不符合，直接返回结果，比递归版本好
if(node.value <= pre){
return false;
}
pre = node.value;
node = node.right;
}
}
return true;
} 4.4 验证满树
如果一棵树是满树，则他的高度是h，节点总计N，则满足N=2ˆh-1
方法一: 递归
需要返回的信息包含: 节点数nodes 和 树的高度 height
base case: ReturnData(0,0)表示空节点，高度为零，节点数也是零
整合信息:height = max(leftHeight, rightHeight) + 1nodes = leftNodes + rightNodes + 1
// 定义递归返回信息类型
public static class ReturnData {
int height;
int num;
ReturnData(int height, int num){
this.height = height;
this.num = num;
}
}
public static ReturnData process (Node root){
// base case
if(root==null){
// 空节点返回(0,0)
return new ReturnData(0,0);
}
// 从左右返回信息
ReturnData leftData = process(root.left);
ReturnData rightData = process(root.right);
// 整合信息
int height = Math.max(leftData.height, rightData.height) + 1;
// 节点总数: 左 + 右 + 自己
int num = leftData.num + rightData.num + 1;
return new ReturnData(height, num);
}
// 最后检查，是否满足公式
public static boolean isFull (Node root){
if(root == null){
return true;
}
ReturnData data = process(root);
// 1 << N 表示 2的N次幂
boolean res = data.num == (1 << data.height) - 1;
System.out.println(data.num);
System.out.println(data.height);
return res;
} 方法二: 层次遍历，统计高度和总的节点数
// 非递归方法: 层次遍历，用HashMap记录，每个节点的层数，最后一个节点的层数，雨总的节点数对比
public static boolean isFull_LevelOrder(Node root) {
if(root == null){
return true;
}
// 队列用于层次遍历
Queue<Node> queue = new LinkedList<Node>();
// HashMap用于记录层数
HashMap<Node, Integer> levelMap = new HashMap<>();
queue.offer(root);
levelMap.put(root, 1);
int curLevel = 0;
Node node = root;
while(!queue.isEmpty()){
node = queue.poll();
curLevel = levelMap.get(node);
if(node.left!=null){
queue.offer(node.left);
levelMap.put(node.left, curLevel+1);
}
if(node.right!=null){
queue.offer(node.right);
levelMap.put(node.right, curLevel+1);
}
}
// 检查最后一层的节点，哈希表的size就是总共的节点数
int num = levelMap.size();
System.out.println(curLevel);
return num == (1 << curLevel) - 1;
} 4.5 验证完全二叉树
方法一: 判定节点
定义: 完全二叉树是满树，或正在依次变成满树
判定条件如下:
- 层次遍历每个节点，如果遇到第一个"孩子不双全的节点",后序的节点都必须是叶节点
- 遍历的每个节点，不能是"有右无左"，不然立刻判定
false
伪代码:
不双全节点标志位:
当left!=null && right==null 时，leaf_flag = true
遇到左空右有的节点:left==null && right!=null
遇到不全节点后，必须是叶子结点leaf && !(left==null && right==null)
public static boolean isCompTree_1 (Node root){
// 层次遍历
if(root==null){
return false;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
boolean isLeaf = false;
while(!queue.isEmpty()){
Node node = queue.poll();
// 遇到孩子不完全的结点后，所有的后序节点必须是叶子结点
// 遇到左空右有的节点，直接返回 false
if( ( isLeaf && !(node.left==null&&node.right==null)) || (node.left==null && node.right!=null)){
return false;
}
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
// 判断叶子结点，遇到不双全的节点
if( node.left!=null && node.right==null){
isLeaf = true;
}
}
return true;
} 5. 非递归的前中后序遍历
非递归遍历是进阶遍历的一种
5.1 先序
准备一个栈
初始化：root入栈
- 出栈cur并打印
- 检查cur的左右子树，如果有，先右子树，再左子树的入栈
- 重复1和2，直到栈为空
代码:
// 1. 非递归先序遍历
/*
额外空间： 新建一个栈
时间复杂度：O(n)
初始化：将root压入栈
1. 将cur弹出栈，并打印
2. 如果cur的左右子树存在，先压入右，再压入左[弹出的时候就是：先左后右]
3. 重复1，2直到栈为空
*/
public static void preOrderUnRecur(Node head){
// 新建一个自己的栈，先压入头节点
System.out.print("Pre-order: ");
if(head==null){
return;
}
Stack<Node> stack = new Stack<Node>();
stack.push(head);
// 只要栈不为空，就压入栈顶的左右孩子(如果有), 然后再弹出栈顶
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();
} 5.2 中序
额外空间：一个栈
时间复杂度： o(n)
初始化：node!=NULL
- 把树的左边界压入栈中[若cur的左子树存在，不停的压入，更新
cur=cur.left]，直到最后的左叶子停止，转到步骤2； - 弹出cur，打印，cur更新为cur->right[检查右子树]，若不为空，重复步骤1，若为空，重复步骤2；
- 直到stack为空，结束
public static void inOrderUnRecur(Node head){
// 中序遍历的终止条件特殊，当栈里没有元素时，可能只是把所有的左子树弹出了，还有右子树没有添加
// 真正的停止条件是: stack为空，且 要添加的右子树为空
System.out.print("In-order: ");
if(head==null){
return;
}
Stack<Node> stack = new Stack<Node>();
while(!stack.isEmpty() || head!=null){
// 一直添加左子树
if(head!=null){
stack.push(head);
head = head.left;
}
// 若head为空，则已经添加到最左边了，检查这个节点
// 先弹出这个节点，因为它的左子树已经遍历结束了
// 对右子树也进行，左遍历，分两个情况:
// 1. 右子树为空，弹出栈中祖父节点(head作为该祖父节点的左子树已经全部处理完了)
// 2. 右子树不为空，重复之前的左遍历
else{
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
System.out.println();
} 5.3 后序
额外空间：两个栈
时间复杂度： o(n)
初始化：stack1压入root
思路：模仿PreOrder的顺序，它弹出顺序[中-左-右]，要对其修改
- stack1弹出cur，不打印，stack2收集弹出的元素
- 若cur的左右子树存在，先压入左子树，再压入右子树[弹出顺序：中-右-左]
- 重复过程1，2，直到stack1为空
- 从栈顶依次弹出stack2的所有元素[相对弹出左-右-中]
public static void postOrderUnRecur(Node head){
// 参考先序遍历的 根左右
// 后序遍历遍历是 左右根，因此先弄出 根右左 用一个栈接住再依次输出
System.out.print("Post-order: ");
if(head==null){
return;
}
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.add(head);
while (!s1.isEmpty()) {
// s1 弹出
head = s1.pop();
// s2 接住
s2.push(head);
// 注意添加顺序，先left再right
if(head.left!=null){
s1.push(head.left);
}
if(head.right!=null){
s1.push(head.right);
}
}
while(!s2.isEmpty()){
head = s2.pop();
System.out.print(head.value + " ");
}
System.out.println();
} 6. 层次输出打印
示例：
二叉树
3
/ \
9 20
/ \
15 7返回其层次遍历结果：
[ [3],[9,20],[15,7] ]
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)
解法:
每次迭代，都可以把整层节点进行操作，这个操作包括:入list 和 添加左右孩子到队列中
- 首先根元素入队
- 当队列不为空的时候
求当前队列的长度 length
依次从队列中取length个元素进行操作，然后进入下一次迭代
public List<List<Integer>> levelOrder(TreeNode root) {
TreeNode node = root;
List<List<Integer>> lists = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root==null){
return lists;
}
queue.offer(node);
// 层次遍历
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new LinkedList<>();
// 一次性压入整层节点
for(int i=0; i<size; i++){
node = queue.poll();
list.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
lists.add(list);
}
return lists;
} 
京公网安备 11010502036488号