Skip to content

Latest commit

 

History

History
112 lines (91 loc) · 3.19 KB

222.md

File metadata and controls

112 lines (91 loc) · 3.19 KB

✏️Leetcode之PHP版题目解析（222. Count Complete Tree Nodes)

2020-05-18 吴亲库里 库里的深夜食堂

✏️描述

给定一棵完全二叉树,求此完全二叉树的节点个数

✏️题目实例

​ ****

✏️题目分析

可以使用递归一个个的计算节点,一行代码干净,但是时间复杂度在O(n),需要全遍历一遍

✏️代码实现1

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function countNodes($root) {
        return $root !=null ?1+$this->countNodes($root->left)+$this->countNodes($root->right):0;
    }

再想想,题目给的是完全二叉树,完全二叉树的特点是什么?除了最后一层(暂且称之为K),其他每层的节点都是满的,并且最后一层的节点全部靠左 也就是说我们其实是在求最后一层的节点数是多少,因为前面0到K-1层的节点是满的,那么利用此树的特性,除最后一层外的所有节点数就是2^d-1(d表示树的高度),对于最后一层我们可以通过二分查找的方式解决,因为最后一层都是靠左的,我只要检查第index 个节点存不存在,存在就向右靠,不存在即右边已经没有了,像左靠.具体看代码

✏️代码实现1

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */




class Solution {
    

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function countNodes($root) {
        if(!$root) return 0;
        $dep=$this->depthNodes($root);
        if($dep==0) return 1;
        $left=1;$right=pow(2,$dep)-1;
        while($left<=$right){
            $middle=$left+floor(($right-$left)/2);
            if($this->hasNode($middle,$dep,$root)){
                $left=$middle+1;
            }else{
                $right=$middle-1;
            }
        }
        return pow(2,$dep)-1+$left;
        
    }
    
    function depthNodes($node)
    {
        $dep=0;
        while($node->left !=null){
            $node=$node->left;
            ++$dep;
        }
        return $dep;
    }
    
    function hasNode($middle,$d,$node)
    {
        $left=0;$right=pow(2,$d)-1;
        for($i=0;$i<$d;++$i){
            $pow=$left+floor(($right-$left)/2);
            if($middle<=$pow){
                $node=$node->left;
                $right=$pow;
            }else{
                $node=$node->right;
                $left=$pow+1;
            }
        }
        return $node !=null;
    }
}

联系

​