目录
树的遍历
题一：如何给二叉树的所有节点数值加一？
题二：Leetcode 100 如何判断两颗二叉树是否相同？
题三：判断一棵树是否是排序二叉树
题四：序列化、反序列化一个二叉树
动态规划
举例：斐波那序列
题一：凑零钱问题
算法 树的遍历 题一：如何给二叉树的所有节点数值加一？
换个说法就是遍历每个节点，然后每个节点值 + 1；
实现方式就是树的遍历：【前、中、后序遍历】
public void traverseHelper(MyNode node){
if (node==null){
return;
}
//前序遍历
traverseHelper(node.left);
//中序遍历
traverseHelper(node.right);
//后续遍历
}
所以题一的解为：
public void NodePlus(TreeNode node) {
if (node == null) {
return;
}
//node.value = node.value + 1;
NodePlus(node.left);
//node.value = node.value + 1;
NodePlus(node.right);
node.value = node.value + 1;
}
题二：Leetcode 100 如何判断两颗二叉树是否相同？
这题的思路还是树的遍历，只是在遍历的基础上添加了判断的条件。对比一二题可以总结出树遍历的方法：递归
题二的解为：
public static boolean isSameBST(TreeNode one, TreeNode two) {
if (one == null && two == null) {
return true;
}
if (one == null || two == null) {
return false;
}
if (one.value != two.value) {
return false;
}
// 上面是判断条件，下面两条递归语句就是树的遍历的核心
boolean s1 = isSameBST(one.left, two.left);
boolean s2 = isSameBST(one.right, two.right);
return s1 && s2;
}
// 测试类
public static void main(String[] args) {
TreeNode node1 = new TreeNode(2);
node1.left = new TreeNode(1);
node1.right = new TreeNode(2);
TreeNode node2 = new TreeNode(2);
node2.left = new TreeNode(1);
node2.right = new TreeNode(3);
System.out.println(isSameBST(node1, node2));
}
题三：判断一棵树是否是排序二叉树
LeetCode：98. 验证二叉搜索树
力扣
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
思路：树的遍历，遍历每个节点时带上父节点的值，所以需要 bstHelper 方法提供父节点的信息。
public static boolean isBST(TreeNode treeNode) {
return bstHelper(treeNode, null, null);
}
private static boolean bstHelper(TreeNode currentNode, TreeNode maxNode, TreeNode minNode) {
if (currentNode == null) {
return true;
}
if (maxNode != null && currentNode.value => maxNode.value) {
return false;
}
if (minNode!=null &¤tNode.value <= minNode.value) {
return false;
}
boolean b1 = bstHelper(currentNode.left, currentNode, minNode);
boolean b2 = bstHelper(currentNode.right, maxNode, currentNode);
return b1 && b2;
}
// 测试类
public static void main(String[] args) {
TreeNode node = new TreeNode(2);
node.left = new TreeNode(1);
node.right = new TreeNode(4);
System.out.println(isBST(node));
}
题四：序列化、反序列化一个二叉树
剑指 Offer 37. 序列化二叉树
力扣
实现一个二叉树可以被序列化为一个字符串，并且可以将这个字符串反序列化为原始的树结构。
关键：不能只通过一种排序算法确定树的结构，确定树的结构需要两种遍历才可以【前中、前后】
结论：序列化的时候加上 空子树的标志
private static linkedList动态规划list = new linkedList<>(); // 序列化:遍历每个节点值存到 linkedList 里 public static void serialize(TreeNode node){ if (node==null){ list.add(-1); return; } list.add(node.value); serialize(node.left); serialize(node.right); } // 反序列化：从 linkedList 里取出值还原成树 public static TreeNode deSerialize(linkedList deList){ Integer first = deList.removeFirst(); if (first==-1){ return null; } TreeNode node = new TreeNode(first); node.left = deSerialize(deList); node.right = deSerialize(deList); return node; } // 测试类 public static void main(String[] args) { // 使用平衡二叉树（上一篇文章中有代码实现） AVLTree tree = new AVLTree(); tree.insert(new TreeNode(2)); tree.insert(new TreeNode(1)); tree.insert(new TreeNode(3)); tree.insert(new TreeNode(6)); tree.insert(new TreeNode(10)); serialize(tree.getRoot()); TreeNode node = deSerialize(list); tree.traverse(node); //这里使用中序遍历，所以输出结果为1 2 3 6 10 }
应用场景：一般都是试求最值的问题
三要素：重叠子问题、最优子结构、状态转移方程
核心：先穷举出所有情况，然后优化问题，数学归纳
举例：斐波那序列
public static int simpleFib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return simpleFib(n - 1) + simpleFib(n - 2);
}
【重叠子问题】：
暴力递归 算法的时间复杂度：子问题个数 * 解决一个子问题所需要的时间 O(2^n)
对上述重叠子问题进行优化：存储子问题结果
public static int cacheFib(int n) {
// 将子问题结果存储到 HashMap 里面
Map cache = new HashMap<>();
return fibHelper(n, cache);
}
private static int fibHelper(int n, Map cache) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
Integer val = cache.get(n);
if (val != null) {
return val;
}
int i = fibHelper(n - 1, cache) + fibHelper(n - 2, cache);
cache.put(n, i);
return i;
}
经过优化之后，时间复杂度退回到常数级别 O(1)
还有一个问题，什么是状态转移方程？
【状态转移方程】：将 f(n) 想成一个状态，则此状态是通过 n-1 的状态与 n-2 的状态转移得到了。
simpleFib(n) = simpleFib(n - 1) + simpleFib(n - 2);
题一：凑零钱问题LeetCode：322. 零钱兑换
力扣
题意：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
例：
count = 11；coins{ 1, 2, 5 }
找规律：
要想求出金额为 11 的最少硬币数，只需求出金额为 10 的最少硬币数（2）然后再加 1 = 3
同理要想求金额为 8 的最小硬币数，只需求出金额为 7 的最小硬币数（2）然后再加 1 = 3
【最优子结构】：向上面这种：子问题之间状态独立，且有最优解的结构
public static int coinsChange(int[] coins, int totalMoney) {
// 动态规划都有：边界问题
if (coins.length == 0) {
return -1;
}
// 数组用于存储每个 count 的最小硬币数
int[] memo = new int[totalMoney + 1];
memo[0] = 0;
// 第一重循环为 count 总金额循环
for (int i = 1; i <= totalMoney; i++) {
int min = Integer.MAX_VALUE;
// 第二重循环为 coin 硬币面值循环
for (int j = 0; j < coins.length; j++) {
int k = i - coins[j];
if (k >= 0 && memo[k] < min) {
// 要想求出金额为 11 的最少硬币数，
// 只需求出金额为 10 的最少硬币数然后再 + 1
min = memo[k] + 1;
}
}
memo[i] = min;
}
return memo[totalMoney] == Integer.MAX_VALUE ? -1 : memo[totalMoney];
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）