05-BinaryTree
暴力递归就是尝试
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件（base case）
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
1. 先、中、后序遍历
package com.listao.algorithm.class06;
import org.junit.jupiter.api.Test;
import java.util.HashMap;
/**
* 遍历二叉树
* Traversal: 遍历
*/
public class _03_BinaryTree {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int v) {
val = v;
}
}
/**
* 递归序
* <p>
* 每个节点在这个方法要经历三次
* 1. 经历第一次就是前序
* 2. 经历第二次就是中序
* 3. 经历第三次就是后序
*/
public static void f(TreeNode head) {
if (head == null) {
return;
}
// 1.
f(head.left);
// 2.
f(head.right);
// 3.
}
/**
* 先序遍历
*/
public static void pre(TreeNode head) {
if (head == null) {
return;
}
System.out.println(head.val);
pre(head.left);
pre(head.right);
}
/**
* 中序遍历
*/
public static void in(TreeNode head) {
if (head == null) {
return;
}
in(head.left);
System.out.println(head.val);
in(head.right);
}
/**
* 后序遍历
*/
public static void pos(TreeNode head) {
if (head == null) {
return;
}
pos(head.left);
pos(head.right);
System.out.println(head.val);
}
/**
* 先：头 左 右
* 中：左 头 右
* 后：左 右 头
*/
@Test
public void traversal() {
TreeNode head = new TreeNode(1);
head.left = new TreeNode(2);
head.right = new TreeNode(3);
head.left.left = new TreeNode(4);
head.left.right = new TreeNode(5);
head.right.left = new TreeNode(6);
head.right.right = new TreeNode(7);
pre(head);
System.out.println("========");
in(head);
System.out.println("========");
pos(head);
System.out.println("========");
}
// --------------------------- 两树一致 SameTree ---------------------------
/**
* 判断两个树一致
* https://leetcode.com/problems/same-tree
*/
public static boolean isSameTree(TreeNode p, TreeNode q) {
// 一个为null，一个不为null
if (p == null ^ q == null) {
return false;
}
// 都为null
if (p == null && q == null) {
return true;
}
// 都不为空
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
// --------------------------- 镜像树 SymmetricTree ---------------------------
/**
* 镜像树为两棵互为镜像树的合并
*/
public static boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
/**
* 判断一棵树是否是镜面树
* https://leetcode.com/problems/symmetric-tree
*/
public static boolean isMirror(TreeNode h1, TreeNode h2) {
if (h1 == null ^ h2 == null) {
return false;
}
if (h1 == null && h2 == null) {
return true;
}
return h1.val == h2.val && isMirror(h1.left, h2.right) && isMirror(h1.right, h2.left);
}
// --------------------------- 树最大高度 MaximumDepthOfBinaryTree ---------------------------
/**
* 树的最大高度
* https://leetcode.com/problems/maximum-depth-of-binary-tree
*/
public static int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 左树、右树中高度最大的 + 1
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
// --------------------------- 先序、中序遍历，重建一棵树 ---------------------------
/**
* 先序、中序遍历，重建一棵树
* https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
*/
public static TreeNode buildTree1(int[] pre, int[] in) {
if (pre == null || in == null || pre.length != in.length) {
return null;
}
return f(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
/**
* 有一棵树，先序结果pre[L1...R1]，中序结果in[L2...R2]
* 请建出整棵树返回头节点
*/
public static TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
// 左树为null，或右树为null（只有一边树）
if (L1 > R1) {
return null;
}
TreeNode head = new TreeNode(pre[L1]);
if (L1 == R1) {
return head;
}
// 1. 中序遍历中头节点位置（头节点值pre[L1]）
int find = L2;
while (in[find] != pre[L1]) {
find++;
}
head.left = f(pre, L1 + 1, L1 + (find - L2), in, L2, (find - 1));
head.right = f(pre, L1 + (find - L2) + 1, R1, in, find + 1, R2);
return head;
}
public static TreeNode buildTree2(int[] pre, int[] in) {
if (pre == null || in == null || pre.length != in.length) {
return null;
}
// 1. 统计中序遍历每个值在哪里
HashMap<Integer, Integer> valueIndexMap = new HashMap<>();
for (int i = 0; i < in.length; i++) {
valueIndexMap.put(in[i], i);
}
return g(pre, 0, pre.length - 1, in, 0, in.length - 1, valueIndexMap);
}
/**
* 空间换时间。省略遍历行为
*/
public static TreeNode g(int[] pre, int L1, int R1, int[] in, int L2, int R2
, HashMap<Integer, Integer> valueIndexMap) {
if (L1 > R1) {
return null;
}
TreeNode head = new TreeNode(pre[L1]);
if (L1 == R1) {
return head;
}
int find = valueIndexMap.get(pre[L1]);
head.left = g(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, valueIndexMap);
head.right = g(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, valueIndexMap);
return head;
}
}
2. 层序遍历
/**
* 层序遍历（二叉树）
* <p>
* 1. queue的`size()`值即为2步骤执行次数
* 2. 弹出节点，当前节点有左先加左，有右再加右
* <p>
* https://leetcode.com/problems/binary-tree-level-order-traversal-ii
*/
public class _01_BinaryTreeLevelOrderTraversal {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
/**
* [[4, 5, 7], [2, 3], [1]]
*/
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans = new LinkedList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 一次while就是一层
while (!queue.isEmpty()) {
// 本层元素个数
int size = queue.size();
List<Integer> curAns = new LinkedList<>();
// `queue.size()`是动态变化的，必须取出来的int
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.poll();
curAns.add(curNode.val);
// 弹出节点，左右节点按顺序加入
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}
// 逆序
ans.add(0, curAns);
}
return ans;
}
/**
* 1. 栈结构，java本身Stack可以直接实例化
* 2. 双端队列LinkedList也具备stack功能
* 3. 数组 int[]也具备stack功能
* 效率大约：int[] > stack > LinkedList
*/
@Test
public void stack() {
// ------------- Stack -------------
long l = System.currentTimeMillis();
int times = 10_000_000;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < times; i++) {
stack.add(i);
}
while (!stack.empty()) {
int pop = stack.pop();
}
// ------------- LinkedList实现Stack -------------
long stackTime = System.currentTimeMillis();
System.out.println("stack，时间：" + (stackTime - l));
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < times; i++) {
list.add(i);
}
while (!list.isEmpty()) {
int pop = list.pollLast();
}
long linkedListTime = System.currentTimeMillis();
System.out.println("LinkedList，时间：" + (linkedListTime - stackTime));
// ------------- int[]实现Stack -------------
int[] ints = new int[times];
int index = 0;
for (int i = 0; i < times; i++) {
ints[index++] = i;
}
while (index != 0) {
int anInt = ints[--index];
}
long end = System.currentTimeMillis();
System.out.println("int[]，时间：" + (end - linkedListTime));
}
}
3. 平衡二叉树
/**
* 判断是否是平衡二叉树
* 平衡树：左、右子树的高度差<=1
* <p>
* https://leetcode.com/problems/balanced-binary-tree
*/
public class _02_BalancedBinaryTree {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
/**
* 1. 树是否平衡
* 2. 高度
*/
public static class Info {
public boolean isBalanced;
public int height;
public Info(boolean i, int h) {
isBalanced = i;
height = h;
}
}
public static boolean isBalanced(TreeNode root) {
return process(root).isBalanced;
}
public static Info process(TreeNode root) {
if (root == null) {
return new Info(true, 0);
}
Info leftInfo = process(root.left);
Info rightInfo = process(root.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
&& Math.abs(leftInfo.height - rightInfo.height) < 2;
return new Info(isBalanced, height);
}
}
4. 二叉搜索树
/**
* 判断是否是二叉搜索树
* <p>
* 1. 中序遍历，严格递增
* 2. 左节点小，右节点大
*/
public class _03_BinarySearchTree {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public static class Info {
public boolean isBST;
// 返回值左右树没有产生调用差异
public int max;
public int min;
public Info(boolean is, int ma, int mi) {
isBST = is;
max = ma;
min = mi;
}
}
/**
* 手写
*/
public static Info process(TreeNode x) {
// baseCase
if (x == null) {
return null;
}
// 左右树info
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int max = x.val;
int min = x.val;
// max min归位
if (leftInfo != null) {
max = Math.max(leftInfo.max, max);
min = Math.min(leftInfo.min, min);
}
if (rightInfo != null) {
max = Math.max(rightInfo.max, max);
min = Math.min(rightInfo.min, min);
}
boolean isBST = true;
if (leftInfo != null && !leftInfo.isBST) {
isBST = false;
}
if (rightInfo != null && !rightInfo.isBST) {
isBST = false;
}
// 判断 左 < 中 < 右
boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
if (!(leftMaxLessX && rightMinMoreX)) {
isBST = false;
}
return new Info(isBST, max, min);
}
}
5. 路径和
/**
* 路径和问题
* 从rootNode到leafNode，一条路径上node和，等于指定值
* <p>
* https://leetcode.com/problems/path-sum
*/
public class _04_PathSum {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public static boolean isSum = false;
public static boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
// 起点，将全局变量false
isSum = false;
process(root, 0, sum);
return isSum;
}
public static void process(TreeNode x, int preSum, int sum) {
// base case
if (x.left == null && x.right == null) {
if (x.val + preSum == sum) {
isSum = true;
}
return;
}
// x是非叶节点
preSum += x.val;
if (x.left != null) {
process(x.left, preSum, sum);
}
if (x.right != null) {
process(x.right, preSum, sum);
}
}
// ------------------------------------------------------------------------
/**
* 标准版
*/
public static boolean hasPathSum2(TreeNode root, int sum) {
if (root == null) {
return false;
}
return process2(root, sum);
}
/**
* 标准版
*/
public static boolean process2(TreeNode root, int rest) {
if (root.left == null && root.right == null) {
return root.val == rest;
}
boolean ans = root.left != null && process2(root.left, rest - root.val);
ans |= root.right != null && process2(root.right, rest - root.val);
return ans;
}
}
/**
* 收集达标路径和
* <p>
* https://leetcode.com/problems/path-sum-ii
*/
public class _05_PathSums {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
ArrayList<Integer> path = new ArrayList<>();
process(root, path, 0, sum, ans);
return ans;
}
public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
if (x.left == null && x.right == null) { // leafNode
// 结束条件
if (preSum + x.val == sum) {
path.add(x.val);
ans.add(new ArrayList<>(path));
// 处理完leafNode，返回其到父node
path.remove(path.size() - 1);
}
return;
}
// 非leafNode
path.add(x.val);
preSum += x.val;
if (x.left != null) {
process(x.left, path, preSum, sum, ans);
}
if (x.right != null) {
process(x.right, path, preSum, sum, ans);
}
// 处理完Node，返回其到父node
path.remove(path.size() - 1);
}
}