品牌网站首页设计,建设通网站有法律,免费ps软件手机版,网页设计网站建设的书籍本系列为笔者的 Leetcode 刷题记录#xff0c;顺序为 Hot 100 题官方顺序#xff0c;根据标签命名#xff0c;记录笔者总结的做题思路#xff0c;附部分代码解释和疑问解答#xff0c;01~07为C语言#xff0c;08及以后为Java语言。
01 二叉树展开为链表 /*** Definition…本系列为笔者的 Leetcode 刷题记录顺序为 Hot 100 题官方顺序根据标签命名记录笔者总结的做题思路附部分代码解释和疑问解答01~07为C语言08及以后为Java语言。
01 二叉树展开为链表 /*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public void flatten(TreeNode root) {}
}方法一递归
class Solution {public void flatten(TreeNode root) {ListTreeNode list new ArrayList();preOrder(root, list);//⭐int size list.size();for(int i1; isize; i){TreeNode prev list.get(i-1);TreeNode curr list.get(i);prev.left null;prev.right curr;}}public void preOrder(TreeNode root, ListTreeNode list){if(root null){return;}list.add(root);preOrder(root.left, list);preOrder(root.right, list);}
}方法二栈
class Solution {public void flatten(TreeNode root) {ListTreeNode list new ArrayList();DequeTreeNode stack new LinkedList();while(root ! null || !stack.isEmpty()){while(root ! null){list.add(root);stack.push(root);root root.left;}root stack.pop();root root.right;}//⭐int size list.size();for(int i1; isize; i){TreeNode prev list.get(i-1);TreeNode curr list.get(i);prev.left null;prev.right curr;}}
}方法三改良版栈
class Solution {public void flatten(TreeNode root) {if(root null){return;}DequeTreeNode stack new LinkedList();stack.push(root);TreeNode prev null;while(!stack.isEmpty()){TreeNode curr stack.pop();if(prev ! null){prev.left null;prev.right curr;}TreeNode left curr.left;TreeNode right curr.right;if(right ! null){stack.push(right);}if(left ! null){stack.push(left);}prev curr;}}
}方法四寻找前驱结点
class Solution {public void flatten(TreeNode root) {TreeNode curr root;while(curr ! null){if(curr.left ! null){TreeNode prev curr.left;while(prev.right ! null){prev prev.right;}prev.right curr.right;curr.right curr.left;curr.left null;}curr curr.right;}}
}02 从前序与中序遍历序列构造二叉树 /*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {}
}方法一递归
class Solution {MapInteger, Integer indexMap; //值下标public TreeNode myBuildTree(int[] preorder, int[] inorder, int prel, int prer, int inl, int inr){if(prel prer){return null;}int pre_root prel; //前序根节点下标int in_root indexMap.get(preorder[prel]); //中序根节点下标TreeNode root new TreeNode(preorder[prel]); //⭐int size in_root - inl;root.left myBuildTree(preorder, inorder, prel1, prelsize, inl, in_root-1);root.right myBuildTree(preorder, inorder, prelsize1, prer, in_root1, inr);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n preorder.length;indexMap new HashMap();for(int i0; in; i){indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n-1, 0, n-1);}
}问题答案简述1. 为什么要建立哈希表为了快速定位根节点在中序数组的位置避免线性查找提高时间效率。2. 为什么 indexMap 要全局定义递归层层调用都需要访问定义为全局成员变量方便统一管理避免反复传参或创建。3. 为什么比较 prel 和 prer 判断递归结束递归分割以前序序列区域为准prel prer时表示无节点终止递归更准确。
03 路径总和 Ⅲ /*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public int pathSum(TreeNode root, int targetSum) {}
}方法一递归
class Solution {public int pathSum(TreeNode root, long targetSum) {if(root null){return 0;}int ret rootSum(root, targetSum);ret pathSum(root.left, targetSum);ret pathSum(root.right, targetSum);return ret;}public int rootSum(TreeNode root, long targetSum){if(root null){return 0;}int ret 0;int val root.val;if(val targetSum){ret;}ret rootSum(root.left, targetSum - val);ret rootSum(root.right, targetSum - val);return ret;}
}方法二前缀和
class Solution {public int pathSum(TreeNode root, long targetSum) {MapLong, Integer prefix new HashMap(); //当前路径总和出现次数prefix.put(0L, 1);return dfs(root, prefix, 0, targetSum);}public int dfs(TreeNode root, MapLong, Integer prefix, long curr, long targetSum){if(root null){return 0;}int ret 0;curr root.val;ret prefix.getOrDefault(curr-targetSum, 0);prefix.put(curr, prefix.getOrDefault(curr, 0) 1); ret dfs(root.left, prefix, curr, targetSum);ret dfs(root.right, prefix, curr, targetSum);prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);return ret;}
}① prefix.getOrDefault(curr, 0) 为啥是0啊
prefix.getOrDefault(curr, 0) 的作用是取出当前前缀和 curr 在哈希表里出现的次数。如果这个 curr 第一次出现prefix 里就没有对应的key因此用 getOrDefault(curr, 0) 返回默认值0表示之前没有出现过这个前缀和。
② prefix.put(curr, prefix.get(curr) - 1);为啥呀
当左、右子树递归完成后递归函数就要回退到父节点继续处理父节点的其他分支 / 返回父节点。 如果不将当前路径和 curr 的出现次数 -1那么在返回父节点后哈希表会错误地保留了当前路径的状态导致其他路径的统计被污染出现错误的计数。
③ prefix.put(curr, prefix.getOrDefault(curr, 0) 1);这里是不断更新吗
是的
prefix.put(curr, prefix.getOrDefault(curr, 0) 1);这行代码是在递归过程中不断更新当前路径和 curr 出现的次数。
04 二叉树的最近公共祖先 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {}
}方法一递归
class Solution {private TreeNode ans;public Solution(){this.ans null;}//1.创建递归方法dfspublic boolean dfs(TreeNode root, TreeNode p, TreeNode q){if(root null){return false;}//2.左右孩子结点boolean lson dfs(root.left, p, q);boolean rson dfs(root.right, p, q);//⭐if((lson rson) || ((root.val p.val || root.val q.val) (lson || rson))){ans root;}//3.return包含递归式return lson || rson || (root.val p.val || root.val q.val);}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {this.dfs(root, p, q);return this.ans;}
}① ans 和 dfs 为啥都是 private
把实现细节隐藏起来不希望外部代码直接访问递归实现细节和存储结果的变量避免外部误用或者干扰。ans 是实现变量dfs 是实现细节的递归函数外部只需调用公开接口 lowestCommonAncestor。
② 为啥ans一旦赋值不会改变
dfs 从树的根节点开始递归访问左右子树后回到根节点。这是一种自底向上的查找方式——当递归顺序回溯到某个节点时说明这个节点是中间某一层的节点。并且最近公共祖先是“最低”的公共祖先即离 p 和 q 最近的那个节点。
05 二叉树中的最大路径和 /*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public int maxPathSum(TreeNode root) {}
}方法递归
class Solution {int max Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {myFunction(root);return max;}public int myFunction(TreeNode root){if(root null){return 0;}int L Math.max(0, myFunction(root.left));int R Math.max(0, myFunction(root.right));//⭐max Math.max(max, L R root.val);return Math.max(L, R) root.val;}
}万一 root.val 是负的怎么办
如果 root.val 是负数我们也必须加上它因为这是这个路径的「根」路径中必须包含它因为题目定义路径一定是一个起点到终点连续的节点链所以这个 L R root.val 是整条路径必须包含的值。
