654.最大二叉树
题目描述
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为 nums 中的 最大值 。
- 递归地在 最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在 最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
解题思路
递归分治
定义一个递归函数construct(nums, left, right)，用来构建 nums[left] 到 nums[right] 这些节点形成的树：
- 首先，找到区间 [left,right] 中最大值的位置maxIdx，创建值为 nums[maxIdx] 的节点作为根节点；
- 然后，开始递归地构造根节点的左子树和右子树：
- 左子树为 construct(nums, left, maxIdx-1)
- 右子树为construct(nums, maxIdx+1, right)
代码实现：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var constructMaximumBinaryTree = function(nums) {
//递归函数
function f(nums,left,right){
if(left>right){
return null;
}
let maxIdx = left;
//找到区间中的最大值位置
for(let i=left+1;i<=right;i++){
if(nums[i]>nums[maxIdx]){
maxIdx = i;
}
}
let node = new TreeNode(nums[maxIdx]);
node.left = f(nums,left,maxIdx-1); //构建左子树
node.right = f(nums,maxIdx+1,right); //构建右子树
return node;
}
return f(nums,0,nums.length-1);
};
单调栈
我们从左往右遍历nums，定义当前遍历的元素为newNode，需要与newNode进行比较的节点为cur，可以保证前面操作的节点都位于newNode的左边。另外，用一个Map来存储各个节点的父节点（如果存在父节点）。遍历过程中的操作如下：
- 若当前节点的值小于前一个节点，它应该添加到前一个节点的右子树；
- 若当前节点的值大于前一个节点，它应该往上寻找父节点直到遇到一个大于当前节点值的父节点cur，而使用pre来保存前一个父节点。找到后，将pre添加到newNode的左子树，因为以pre为根的子树的所有节点的值都小于newNode且位于newNode的左边。
- 如果cur不为undefined，表示存在比当前节点值大的节点，应该将当前节点添加到cur的右子树，同时保存两节点的父子关系到parent中；
- 如果cur为undefined，表示当前节点值最大，应该作为整个数的根节点，因此将之前的根节点添加到newNode的左子树，并更新root。
代码如下：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var constructMaximumBinaryTree = function(nums) {
const parent = new Map();//用于保存节点间父子关系的Map
//初始化，先将nums[0]作为根节点
let root = new TreeNode(nums[0]);
let cur = root;
for(let i=1;i<nums.length;i++){
let newNode = new TreeNode(nums[i]);
if(nums[i]<nums[i-1]){
cur.right = newNode;
parent.set(newNode,cur);
}else{
let pre = null; //pre保存搜索过程中的前一个父节点
//找到比nums[i]大的父节点，最后找不到时get()返回的是undefined
while(cur!==undefined&&nums[i]>cur.val){
pre = cur;
cur = parent.get(cur);
}
newNode.left = pre;
parent.set(pre,newNode);
//当找到了比nums[i]大的父节点cur，把newNode添加到cur的右子树
if(cur!==undefined){
cur.right = newNode;
parent.set(newNode,cur); //添加父子关系
}else{ //若找不到符合的父节点，表示nums[i]值最大，它应该作为新的根节点
root = newNode;
}
}
cur = newNode;//更新cur为当前元素，方便后面遍历的元素进行重新比较
}
return root;
};
998.最大二叉树II
题目描述
假设给定了一个数组a，通过《654.最大二叉树》中定义的方法构建好一棵最大二叉树，其根节点为root。现在，在数组a的末尾添加一个值val，形成了新的数组b，如何在已知root和val的基础上，构建新的最大二叉树？
解题思路
定义一个递归函数f，返回值为重建的最大二叉树的根节点。
首先将val与root.val比较，
- 若val>root.val，那么新节点node应该作为新的根节点，而已构建好的最大二叉树的根节点root应该添加到node的左子树（因为node在数组b中始终位于最右边）；
- 若val<root.val，由于node在数组b中始终位于最右边，那么node应该放置在root的右子树上，表示右子树需要重建，将重建后的新根子节点添加到当前root的右子树。如何得到重建后的新根子节点呢？只需要继续遍历右子树，也即更新root为root.right，重复上述操作。
代码如下：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var insertIntoMaxTree = function(root, val) {
function f(root,val){
if(val>root.val){
let node = new TreeNode(val);
node.left = root;
return node; //根节点改变了
}else{
if(root.right){
let subRoot = f(root.right,val); //获取某右子树重建后的根节点
root.right = subRoot;
}else{
let node = new TreeNode(val);
root.right = node;
}
return root; //根节点没有改变，直接返回
}
}
return f(root,val);
};
标签：right,val,nums,II,654,二叉树,root,节点,left From： https://www.cnblogs.com/evil-shark/p/16639566.html