LeetCode热题100JS（49/100）第九天|199|114|105|437|236

 199. 二叉树的右视图

标题链接：199. 二叉树的右视图
   难度：中等
  刷题状态：2刷
  新知识：
  解题过程

思索

示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：

放下1刷过程在题解
题解分析

参考题解链接：【视频】如何机动运用递归？（Python/Java/C++/Go/JS/Rust）
详细分析如下

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val, left, right) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.left = (left===undefined ? null : left)
6. *     this.right = (right===undefined ? null : right)
7. * }
8. */
9. /**
10. * @param {TreeNode} root
11. * @return {number[]}
12. */
14. var rightSideView = function(root) {
15.     if(!root){
16.         return []
17.     }
18.     let res=[]
19.     function rightDepth(node,depth){
20.         if(!node){
21.             return
22.         }
23.         if(depth==res.length){
24.             res.push(node.val)
25.         }
26.         rightDepth(node.right,depth+1)
27.         rightDepth(node.left,depth+1)
28.     }
29.     rightDepth(root,0)
30.     return res
31. };

复制代码

手搓答案（无非废话版）

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val, left, right) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.left = (left===undefined ? null : left)
6. *     this.right = (right===undefined ? null : right)
7. * }
8. */
9. /**
10. * @param {TreeNode} root
11. * @return {number[]}
12. */
14. var rightSideView = function(root) {
15.     let res=[]
16.     function dfs(node,depth){
17.         if(!node) return
18.         if(res.length==depth) res.push(node.val)
19.         dfs(node.right,depth+1)
20.         dfs(node.left,depth+1)
21.     }
22.     dfs(root,0)
23.     return res
24. };

复制代码

总结

 可以用res.length==depth来判定是否传入数据，注意right要先递归，如许才是传入右边的数据
 114. 二叉树展开为链表

标题链接：​​​​​​​​​​​​​​114. 二叉树展开为链表
   难度：中等
  刷题状态：1刷
  新知识：
  解题过程

思索

示例 1：

1. <strong>输入：</strong>root = [1,2,5,3,4,null,6]
2. <strong>输出：</strong>[1,null,2,null,3,null,4,null,5,null,6]

复制代码

题解分析

参考题解链接：​​​​​​​详细通俗的思路分析，多解法​​​​​​​
详细分析如下

2. /**
3. * Definition for a binary tree node.
4. * function TreeNode(val, left, right) {
5. *     this.val = (val===undefined ? 0 : val)
6. *     this.left = (left===undefined ? null : left)
7. *     this.right = (right===undefined ? null : right)
8. * }
9. */
10. /**
11. * @param {TreeNode} root
12. * @return {void} Do not return anything, modify root in-place instead.
13. */
14. var flatten = function(root) {
15.     let pre=null
16.     function dfs(node){
17.         if(!node) return
18.         首先递归地遍历当前节点的右子树。由于目标是构建右斜树，所以先处理右子树有助于保持相对顺序。
19.         dfs(node.right)
20.         dfs(node.left)
21.         //将当前节点的右子节点设置为 pre，即前一个节点。这一步是构建右斜树的关键，它将当前节点的左子树之前的所有节点链接起来。
22.         node.right=pre
23.         //更新 pre 为当前节点。这样，在下一次迭代中，当前节点将成为下一个节点的“前一个节点”。
24.         pre=node
25.         node.left=null
26.     }
27.     dfs(root)
28. };

复制代码

手搓答案（无非废话版）

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val, left, right) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.left = (left===undefined ? null : left)
6. *     this.right = (right===undefined ? null : right)
7. * }
8. */
9. /**
10. * @param {TreeNode} root
11. * @return {void} Do not return anything, modify root in-place instead.
12. */
13. var flatten = function(root) {
14.     let pre=null
15.     function dfs(node){
16.         if(!node) return
17.         dfs(node.right)
18.         dfs(node.left)
19.         node.right=pre
20.         pre=node
21.         node.left=null
22.     }
23.     dfs(root)
24. };

复制代码

总结

 可以用res.length==depth来判定是否传入数据，注意right要先递归，如许才是传入右边的数据
 ​​​​​​​​​​​​​​105. 从前序与中序遍历序列构造二叉树

标题链接：​​​​​​​​​​​​​​​​​​​​​​​​​​​​105. 从前序与中序遍历序列构造二叉树
   难度：中等
  刷题状态：2刷
  新知识：
  解题过程

思索

示例 1:

1. <strong>输入</strong><strong>:</strong> preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
2. <strong>输出:</strong> [3,9,20,null,null,15,7]

复制代码

放下1刷过程在题解
题解分析

参考题解链接：​​​​​​​详细通俗的思路分析，多解法​​​​​​​
详细分析如下

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val, left, right) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.left = (left===undefined ? null : left)
6. *     this.right = (right===undefined ? null : right)
7. * }
8. */
9. /**
10. * @param {number[]} preorder
11. * @param {number[]} inorder
12. * @return {TreeNode}
13. */
14. var buildTree = function(preorder, inorder) {
15.     let dic={}
16.     for(let i=0;i<inorder.length;i++){
17.         dic[inorder[i]]=i
18.     }
19.     //开始递归
20.     function dfs(pre,left,right){
21.         if(left>right) return null
22.         //创建根节点
23.         let node=new TreeNode(preorder[pre])
24.         //搜索preorder元素（根节点）在inorder中的索引
25.         let i=dic[preorder[pre]]
26.         //创建左子树
27.         node.left=dfs(pre+1,left,i-1)
28.         //创建右子树
29.         node.right=dfs(pre+1+i-left,i+1,right)
30.         return node
31.     }
32.     return dfs(0,0,inorder.length-1)
33. };

复制代码

手搓答案（无非废话版）

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val, left, right) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.left = (left===undefined ? null : left)
6. *     this.right = (right===undefined ? null : right)
7. * }
8. */
9. /**
10. * @param {number[]} preorder
11. * @param {number[]} inorder
12. * @return {TreeNode}
13. */
14. var buildTree = function(preorder, inorder) {
15.     let dic={}
16.     for(let i=0;i<inorder.length;i++){
17.         dic[inorder[i]]=i
18.     }
19.     function dfs(pre,left,right){
20.         if(left>right) return null
21.         let node=new TreeNode(preorder[pre])
22.         let i=dic[preorder[pre]]
23.         node.left=dfs(pre+1,left,i-1)
24.         node.right=dfs(pre+1+i-left,i+1,right)
25.         return node
26.     }
27.     return dfs(0,0,inorder.length-1)
28. };

复制代码

总结

 重点理解这两行
        node.left=dfs(pre+1,left,i-1)
        node.right=dfs(pre+1+i-left,i+1,right)

• pre+1:
  
  
  
  • 前序遍历中，pre 是当前子树根节点的索引。
    
  • pre+1 是左子树根节点在前序遍历数组中的索引，由于前序遍历紧接着根节点访问左子树。
    
  
  
• left 到 i-1:
  
  
  
  • left 是当前子树在中序遍历中的起始索引。
    
  • i 是根节点在中序遍历中的位置。
    
  • i-1 是左子树在中序遍历中的结束索引。
    
  
  

因此，这一行代码通过递归调用 dfs 构建当前节点的左子树。

• pre+1+i-left:
  
  
  
  • pre+1 是左子树根节点在前序遍历中的起始索引。
    
  • i-left 是左子树中的节点数。
    
  • 因此，pre+1+i-left 是右子树根节点在前序遍历中的起始索引。
    
  
  
• i+1 到 right:
  
  
  
  • i+1 是右子树在中序遍历中的起始索引。
    
  • right 是当前子树在中序遍历中的结束索引。
    
  
  

这一行代码通过递归调用 dfs 构建当前节点的右子树。
 ​​​​​​​437. 路径总和 III

标题链接：​​​​​​​437. 路径总和 III
   难度：中等
  刷题状态：1刷
  新知识：
  解题过程

思索

示例 1：

1. <strong>输入：</strong>root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
2. <strong>输出：</strong>3
3. <strong>解释：</strong>和等于 8 的路径有 3 条，如图所示。

复制代码

题解分析

参考题解链接：【视频】如何机动运用递归？（Python/Java/C++/Go/JS/Rust）
详细分析如下

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val, left, right) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.left = (left===undefined ? null : left)
6. *     this.right = (right===undefined ? null : right)
7. * }
8. */
9. /**
10. * @param {TreeNode} root
11. * @param {number} targetSum
12. * @return {number}
13. */
14. var pathSum = function(root, targetSum) {
15.     let res=0
16.     //用于记录遍历过程中遇到的前缀和及其出现的次数
17.     let cnt=new Map()
18.     //节点和为0的情况有1种
19.     cnt.set(0,1)
20.     //s记录当前路径上的节点之和
21.     function dfs(node,s){
22.         if(!node) return null
23.         s+=node.val
24.         // console.log(s-targetSum,cnt)
25.         if(cnt.get(s-targetSum)){
26.             //如果有，说明某个祖先节点到当前节点的路径和等于 targetSum
27.             res+=cnt.get(s-targetSum)
28.         }
29.         if(!cnt.get(s)) cnt.set(s,0)
30.         cnt.set(s,cnt.get(s)+1)
32.         dfs(node.left,s)
33.         dfs(node.right,s)
34.         //复位
35.         cnt.set(s,cnt.get(s)-1)
36.     }
37.     dfs(root,0)
38.     return res
39. };

复制代码

手搓答案（无非废话版）

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val, left, right) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.left = (left===undefined ? null : left)
6. *     this.right = (right===undefined ? null : right)
7. * }
8. */
9. /**
10. * @param {TreeNode} root
11. * @param {number} targetSum
12. * @return {number}
13. */
14. var pathSum = function(root, targetSum) {
15.     let cnt =new Map(),res=0
16.     cnt.set(0,1)
17.     function dfs(node,s){
18.         if(!node) return null
19.         s+=node.val
20.         if(cnt.get(s-targetSum)){
21.             res+=cnt.get(s-targetSum)
22.         }
23.         if(!cnt.get(s)) cnt.set(s,0)
24.         cnt.set(s,cnt.get(s)+1)
25.         dfs(node.left,s)
26.         dfs(node.right,s)
27.         cnt.set(s,cnt.get(s)-1)
28.     }
29.     dfs(root,0)
30.     return res
31. };

复制代码

总结

 注意要先设置（0，1）的初值
 ​​​​​​​236. 二叉树的最近公共先人

标题链接：​​​​​​​​​​​​​​236. 二叉树的最近公共先人
   难度：中等
  刷题状态：2刷
  新知识：
  解题过程

思索

示例 1：

1. <strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
2. <strong>输出：</strong>3
3. <strong>解释：</strong>节点 5 和节点 1 的最近公共祖先是节点 3 。

复制代码

放下1刷过程在题解
题解分析

参考题解链接：【视频】如何机动运用递归？（Python/Java/C++/Go/JS/Rust）
详细分析如下

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val) {
4. *     this.val = val;
5. *     this.left = this.right = null;
6. * }
7. */
8. /**
9. * @param {TreeNode} root
10. * @param {TreeNode} p
11. * @param {TreeNode} q
12. * @return {TreeNode}
13. */
14. var lowestCommonAncestor = function(root, p, q) {
15.     if(!root||root==p||root==q) return root
16.     //递归地在当前节点的左子树中查找p和q的最低公共祖先，并将结果存储在left变量中。
17.     let left=lowestCommonAncestor(root.left,p,q)
18.     //递归地在当前节点的右子树中查找p和q的最低公共祖先，并将结果存储在right变量中。
19.     let right=lowestCommonAncestor(root.right,p,q)
21.     //这意味着p和q的最低公共祖先在右子树中，或者p和q中的一个就是right节点本身。
22.     if(!left) return right
23.     //这意味着p和q的最低公共祖先在左子树中，或者p和q中的一个就是left节点本身。
24.     if(!right) return left
26.     //如果left和right都不为null，说明p和q分别位于当前节点的左右两侧（或者其中一个就是当前节点）。在这种情况下，返回当前节点作为p和q的最低公共祖先。
27.    
28.     return root
29.     //return left && right ? root : left || right;
30. };

复制代码

手搓答案（无非废话版）

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val) {
4. *     this.val = val;
5. *     this.left = this.right = null;
6. * }
7. */
8. /**
9. * @param {TreeNode} root
10. * @param {TreeNode} p
11. * @param {TreeNode} q
12. * @return {TreeNode}
13. */
14. var lowestCommonAncestor = function(root, p, q) {
15.     if(!root||root==p||root==q) return root
16.     let left=lowestCommonAncestor(root.left,p,q)
17.     let right=lowestCommonAncestor(root.right,p,q)
18.     if(!left) return right
19.     if(!right) return left
20.     return root
21. };

复制代码

总结

 重点理解
    if(!left) return right
    if(!right) return left
这两个逻辑

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。