代码随想录Day20-Leetcode654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

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)
}

看了题解后,发现递归需要设置界限,而非根结点和左右孩子结点比大小