在易语言里面做网站,网站开发有关费用,网站备案上海,WordPress目录和连接关系力扣爆刷第92天之hot100五连刷46-50 文章目录 力扣爆刷第92天之hot100五连刷46-50一、114. 二叉树展开为链表二、105. 从前序与中序遍历序列构造二叉树三、437. 路径总和 III四、236. 二叉树的最近公共祖先五、124. 二叉树中的最大路径和 一、114. 二叉树展开为链表
题目链接https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envTypestudy-plan-v2envIdtop-100-liked 思路采用后序遍历然后把当前节点的左子树赋值给右孩子然后将右孩子复制给左子树最右边的右孩子左子树最右下角的节点是左子树最后遍历的位置那么root的右子树理应接在这个位置。
class Solution {public void flatten(TreeNode root) {if(root null) return;flatten(root.left);flatten(root.right);TreeNode left root.left;TreeNode right root.right;root.left null;root.right left;TreeNode p root;while(p.right ! null) {p p.right;}p.right right;}
}二、105. 从前序与中序遍历序列构造二叉树
题目链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envTypestudy-plan-v2envIdtop-100-liked 思路使用map减少检索根节点在中序遍历中位置的时间然后利用前序中根节点的位置与中序中根节点的位置以及中序中左边界到根节点的距离不断的递归划分数组构造二叉树。
class Solution {MapInteger, Integer map new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i 0; i inorder.length; i) {map.put(inorder[i], i);}return createTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);}TreeNode createTree(int[] preorder, int[] inorder, int left1, int right1, int left2, int right2) {if(left1 right1 || left2 right2) return null;TreeNode root new TreeNode();int mid preorder[left1];root.val mid;int indexO map.get(mid);root.left createTree(preorder, inorder, left11, left1indexO-left2, left2, indexO-1);root.right createTree(preorder, inorder, left1indexO-left21, right1, indexO1, right2);return root;}
}三、437. 路径总和 III
题目链接https://leetcode.cn/problems/path-sum-iii/description/?envTypestudy-plan-v2envIdtop-100-liked 思路只要求路径总和其实都可以考虑前缀和本题更加适合前缀和要求求和的节点只能一路往下不能出现向上向下这种那么在前缀和的构造过程中单节点向左向右都是回溯的进入过程当左右节点都处理完后即为回溯的返回过程这时需要去掉添加的前缀和避免出现向上向下的节点片段。
class Solution {MapLong, Integer map new HashMap();public int pathSum(TreeNode root, int targetSum) {map.put(0L, 1);return preSum(root, 0L, targetSum);}int preSum(TreeNode root, Long cur, int targetSum) {if(root null) return 0;int res 0;cur root.val;res map.getOrDefault(cur - targetSum, 0);map.put(cur, map.getOrDefault(cur, 0)1);res preSum(root.left, cur, targetSum);res preSum(root.right, cur, targetSum);map.put(cur, map.getOrDefault(cur, 0)-1);return res;}
}四、236. 二叉树的最近公共祖先
题目链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envTypestudy-plan-v2envIdtop-100-liked 思路先序遍历遇到相等节点返回如果左右节点都返回值则父节点就是最近公共祖先否则就是左右节点返回的不为空的那一个。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null) return null;if(root p || root q) return root;TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if(left ! null right ! null) return root;return left ! null ? left : right;}
}五、124. 二叉树中的最大路径和
题目链接https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envTypestudy-plan-v2envIdtop-100-liked 思路求二叉树中的最大路径和这种问题采用后序遍历自下而上的记录累加和采用贪心的思想左右子树提供的和必须得大于零才会被使用然后记录下最大值向父节点提供值只能是单边路径。
class Solution {int max Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {order(root);return max;}int order(TreeNode root) {if(root null) return 0;int left Math.max(order(root.left), 0);int right Math.max(order(root.right), 0);int cur left right root.val;max Math.max(max, cur);return root.val Math.max(left, right);}
}
