1. 654.最大二叉树

题目
题解

重点是先把题读明白,先找最大根节点,左边的就是左子树,右边的就是右子树,对子树也进行相同的操作.意思是不是左子树的子节点就都在左边,左子树拿出来最大的比如是第二个元素,那第二个元素右边的元素就得是第二个元素作为根节点的右子树.

凡是构建二叉树的题都要用前序遍历:
因为要先放根节点,也就是中

以及在给的funtion再写function递归是因为,需要传进去别的参数,如果只需要每次递归传root当然可以不用套function

• 本题在找最大点的时候每次递归都是把整个数组传递,只改变left和right的index,从而不断缩小范围.所以不能用math的方法,因为那样返回的是整个数组的结果,除非用slice分两个数组.但是这样会特别慢,可能会超时,因为每个数组都会创建两次.

2. 617.合并二叉树

题目
题解

大体思路知道了,但是不看题解真的不知道怎么操作,比如写着写着情况就越来越多了,我一开始写了这些

 node1.left&&node2.left&&mergeAll(node1.left,node2.left);
 node1.right&&node2.right&&mergeAll(node1.left,node2.left);

这样写写不完了.

题解用的方法是在在一棵树上修改.按规则加或不加另一个树的值.
对于子节点不用那么复杂,左边就都用传进去left,根据返回条件,就算都是null也没事

3. 700.二叉搜索树(BST)中的搜索

题目
题解

这道题思路自己想出来了,但是代码实现有些问题.这是我的版本

var searchBST = function(root, val) {
    const searchNode = function(node){
        if(node.val === val) return node;
        if(node.val >val){
            node.left && searchNode(node.left);
        } 
        if(node.val <val){
            node.right && searchNode(node.right);
        } 
    }
    return searchNode(root)
};

这个版本没法处理node是null的情况,而且也没有返回node,要用return 一层一层向上返回

题解的版本把===val 和!node放一起处理了,因为都是返回node

4.98.验证二叉搜索树

题目
题解

我看到的思考:
要存最大值,每次进的时候比较
进左就要比当前节点小.
不能只有一个子树

我的写法:

var isValidBST = function(root) {
    const BST = function(node){
        if(!node.left&&node.right||node.left&&!node.right) return false;
        if(node.left&&node.left.val>=node.val ||node.right&&node.right.val<=node.val) return false;
        if(node.left){
            return BST(node.left);
        }
        if(node.right){
            return BST(node.right)
        }
        return true
    }
    return BST(root);
};

直接掉进陷阱里了

image.png

• 遇到搜索树,记得用中序遍历,
  中序遍历的特点:输出的节点的数值是有序数列,
  所以验证是不是二叉搜索树就转化为判断序列是不是递增的,递归的时候把值push进辅助数组,判断辅助数组就好了