654.最大二叉树
题目链接:https://leetcode.cn/problems/maximum-binary-tree/
基本的模拟思路很快
/**
* 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) {
return consTree(nums,0,nums.length-1)
};
/**
* @param {number[]} arr
* @return {TreeNode}
*/
function consTree(arr,left,right){
if(left>right){
return null
}
let maxIndex = left;
let max = arr[left]
for(let i = left+1; i<= right;i++){
if(arr[i]>max){
max = arr[i]
maxIndex = i
}
}
let node = new ListNode(max)
node.left = consTree(arr,left,maxIndex-1)
node.right = consTree(arr,maxIndex+1,right)
return node
}
617.合并二叉树
题目链接:https://leetcode.cn/problems/merge-two-binary-trees/
很明显的递归写法,不过效率好低,10%不到;
/**
* 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} root1
* @param {TreeNode} root2
* @return {TreeNode}
*/
var mergeTrees = function(root1, root2) {
if(root1==null){
return root2
}else if(root2 == null){
return root1
}else{
root1.val = root1.val + root2.val
root1.left = mergeTrees(root1.left,root2.left)
root1.right = mergeTrees(root1.right,root2.right)
return root1
}
};
另外好像有bfs的方法,暂略
700.二叉搜索树中的搜索
递归
/**
* 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 searchBST = function(root, val) {
if(root == null){
return null
}
if(val==root.val){
return root
}else if (val>root.val){
return searchBST(root.right,val)
}else{
return searchBST(root.left,val)
}
};
//又犯了经典错误:递归少参数
迭代
不知道怎么回事,力扣上迭代总比递归慢...
/**
* 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 searchBST = function(root, val) {
let node = root
while(node!=null){
if(node.val == val){
return node
}else if(val>node.val){
node = node.right
}else{
node = node.left
}
}
return null
};
98.验证二叉搜索树
用了中序遍历然后投影;
不太清楚怎么递归,感觉子问题不好划分,左右子树都有效的情况下,该树仍可能会无效
/**
* 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
* @return {boolean}
*/
//似乎这个结构并不那么递归?左右子树都有效的情况下,可能会无效
//类似于局部有序不等于整体有序;
//暴力的方法是,直接中序遍历投影,检查是否有序
var isValidBST = function(root) {
let arr = []
inOrder(root,arr)
for(let i =1;i<arr.length;i++){
if(arr[i]<=arr[i-1]){
return false
}
}
return true
};
function inOrder(node,result){
if(node == null){
return
}
inOrder(node.left,result)
result.push(node.val)
inOrder(node.right,result)
}
看了题解后,发现递归需要设置界限,而非根结点和左右孩子结点比大小