LeetCode(剑指 Offer)- 07. 重建二叉树

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
应用型负载均衡 ALB,每月750个小时 15LCU
简介: LeetCode(剑指 Offer)- 07. 重建二叉树

题目链接:点击打开链接

题目大意:

解题思路:

相关企业

  • 字节跳动
  • Facebook
  • 亚马逊(Amazon)
  • 谷歌(Google)
  • 微软(Microsoft)
  • 优步(Uber)
  • 彭博(Bloomberg)


AC 代码

  • Java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/// 解决方案(1)classSolution {
int[] preorder, inorder;
Map<Integer, Integer>inorderMap=newHashMap<>();
publicTreeNodebuildTree(int[] preorder, int[] inorder) {
this.preorder=preorder;
this.inorder=inorder;
for (inti=0; i<inorder.length; i++) {
inorderMap.put(inorder[i], i);
        }
returnrecur(0, inorder.length-1, 0, preorder.length-1);
    }
TreeNoderecur(intla, intra, intlb, intrb) {
if (la>ra) returnnull;
intpreRoot=preorder[lb];
intmidRoot=inorderMap.get(preRoot);
intleftLen=midRoot-la;
TreeNoderoot=newTreeNode(preRoot);
root.left=recur(la, midRoot-1, lb+1, lb+leftLen);
root.right=recur(midRoot+1, ra, lb+leftLen+1, rb);
returnroot;
    }
}
// 解决方案(2)classSolution {
int[] preorder;
HashMap<Integer, Integer>dic=newHashMap<>();
publicTreeNodebuildTree(int[] preorder, int[] inorder) {
this.preorder=preorder;
for(inti=0; i<inorder.length; i++)
dic.put(inorder[i], i);
returnrecur(0, 0, inorder.length-1);
    }
TreeNoderecur(introot, intleft, intright) {
if(left>right) returnnull;                          // 递归终止TreeNodenode=newTreeNode(preorder[root]);          // 建立根节点inti=dic.get(preorder[root]);                       // 划分根节点、左子树、右子树node.left=recur(root+1, left, i-1);              // 开启左子树递归node.right=recur(root+i-left+1, i+1, right); // 开启右子树递归, root + i - left + 1 => root + (left - (i - 1) + 1) + 1 (根节点索引 + 左子树长度 + 1)returnnode;                                           // 回溯返回根节点    }
}
  • C++
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/classSolution {
public:
TreeNode*buildTree(vector<int>&preorder, vector<int>&inorder) {
this->preorder=preorder;
for(inti=0; i<inorder.size(); i++)
dic[inorder[i]] =i;
returnrecur(0, 0, inorder.size() -1);
    }
private:
vector<int>preorder;
unordered_map<int, int>dic;
TreeNode*recur(introot, intleft, intright) { 
if(left>right) returnnullptr;                        // 递归终止TreeNode*node=newTreeNode(preorder[root]);          // 建立根节点inti=dic[preorder[root]];                            // 划分根节点、左子树、右子树node->left=recur(root+1, left, i-1);              // 开启左子树递归node->right=recur(root+i-left+1, i+1, right); // 开启右子树递归, root + i - left + 1 => root + (left - (i - 1) + 1) + 1 (根节点索引 + 左子树长度 + 1)returnnode;                                            // 回溯返回根节点    }
};
相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
目录
相关文章
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
26 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
20 2
|
2月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
18 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
21 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
20 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
21 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
4月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
4月前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历