【算法】合格二叉树——如何做一个孝顺的二叉树

力口力口力~
来一道力口小题
原题链接:https://leetcode-cn.com/probl...

做二叉树难,做一个孝顺的二叉树难的头秃……
那么什么是孝顺的二叉树呢?

孝顺二叉树定义:

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。


示例 1:
输入:

    2
   / \
  1   3

输出: true


示例 2:
输入:

        5
       / \
      1   4
         / \
        3   6

输出: false


解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。


怎么样?是不是觉得这道题其实并不是很难?
但其实定义里包含了一个隐藏信息:除了当前节点的左子节点必须小于当前节点外,其左子节点的所有子孙节点都必须小于当前节点。右子节点同理
当当~
是不是很绕?
再来举个栗子叭:


示例 3:
输入:

        5
       / \
      1   7
         / \
        3   8
        

输出: false


解释: 输入为: [5,1,7,null,null,3,8]。
第三层中的节点3是不合法的,因为它是第二层中7节点的子节点,因此它必须也要大于5


结题思路来了
题主在做这道题一开始走了好多好多弯路,总觉得好简单,但总是卡在了例子3的错误上(头秃……)。
那么其实正确的思路大致应该是:
1、从根节点开始,每次判断自己的左右节点是否为null,
2、不为null再判断是否大于或小于当前节点值,
3、如果正确就再判断当前节点有没有继承过边界(比如根节点就没有边界,第二层右节点的边界就是:左:root/右:undefined)
4、然后判断是否在边界内,
5、如果还正确就将父亲的边界继承给子节点并继续递归子节点的合法性。

直接上答案,详细思路在注视里自己看昂:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(rootTreeNode) {
    //防止传入的节点为null
   return rootTreeNode === null?true:isLegalTreeNode(rootTreeNode);
};
//验证treenode的合法性
var isLegalTreeNode = function(tr){
    //先来判断当前节点的左子节点合不合法
    var _left = false;
    if(tr.left !== null){
        //如果小左是个treenode
        if(tr.left.val < tr.val){
             //小左比当前节点小,好感+1~
            if(tr.leftBoder !== undefined){
                 //当前节点有左边界
                if(tr.left.val > tr.leftBoder){
                     //小左比当前左边界大,好感+1~
                    tr.left.leftBoder = tr.leftBoder; //小左继承当前节点的左边界
                    tr.left.rightBoder = tr.val;//小左的右边界就是当前节点
                    _left = isLegalTreeNode(tr.left);//看看小左的子孙是不是合法的
                }else{
                    _left = false;
                }
            }else{
                tr.left.rightBoder = tr.val;
                _left = isLegalTreeNode(tr.left);
            }
        }else{
            _left = false;
        }
    }else{
        _left = true;
    }
    
    //小右同理~
    var _right = false;
    if(tr.right !== null){
        if(tr.right.val > tr.val){
            if(tr.rightBoder !== undefined){
                if(tr.right.val < tr.rightBoder){
                    tr.right.rightBoder = tr.rightBoder;
                    tr.right.leftBoder = tr.val;
                    _right = isLegalTreeNode(tr.right);
                }else{
                    _right = false;
                }
            }else{
                tr.right.leftBoder = tr.val;
                _right = isLegalTreeNode(tr.right);
            }
        }else{
            _right = false;
        }
    }else{
        _right = true;
    }
    return _left && _right;//最后当小左小右都合法啦,那么当前节点就是合法的
}

是吧?~
满足了所有祖祖辈辈的要求,这岂不是孝顺急了,HHHHHHH~

大家有什么新解法或者优化也可以分享给小楼,虾虾咯~

评论

暂无评论