leetcode222求完全二叉树节点个数

求完全二叉树节点个数

原题地址https://leetcode.com/problems/count-complete-tree-nodes/description/ 思路:先算出树的高度level,找尾节点,看下结尾排列,看下h = 3最后一排的排列,0代表向左子树搜索,1代表向右子树搜索,可以用bit特位表示,可以用二分查找法搜索,每一次从根节点向叶节点查找

#(0,0,0),(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)其实是
0,1,2,3,4,5,6,7
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
  
class Solution(object):
    # 先算数的深度
    def findlevel(self, root):
        if root:
             return 1+self.findlevel(root.left)
        else:
            return 0
    '''step就是用1代表(0,0,1),3'''  
    def findendNode(self, root, step, level):
        #print step,level
        temp = root
        for i in range(level):
            if ((step&(2**(level-1-i))) >> (level-1-i)) == 0:
                #print 'xxx'
                temp = temp.left
            else:
                temp = temp.right
        if temp:
            return True
        else:
            return False
                
    '''
    def findendNode(self, root, step, level):
        temp = root
        lr = list(bin(step))[2:]
        #print 'lr', lr, 'level', level
        lrlen = len(lr)
        # 左子树
        for i in range(level-lrlen):
            temp = temp.left
        for i in range(lrlen):
            if lr[i] == '0':
                temp = temp.left
            else:
                temp = temp.right
        if temp:
            return True
        else:
            return False
    '''    
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        level=self.findlevel(root)-1
        if level == 0:
            return 1
        endend = 2**level
        s = endend - 1
        # 找出深度后呢,找出结尾,看下结尾排列,看下h = 3最后一排的排列,0代表向左子树搜索,1代表向右子树搜索,可以用bit特         # 位表示,可以用二分查找法
        #(0,0,0),(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)其实就是0,1,2,3,4,5,6,7
        start = 0
        end = endend-1
        while True:
            # 从中间找
            temp = (end+start)/2
            if not self.findendNode(root, temp, level):
                # 如果是false,设置为end
                end = temp
            else:
                # 如果是true,设置为起点
                start = temp
            if end-start == 1:
                if end == endend-1:
                    if self.findendNode(root, end, level):
                        s += endend
                        return s
                    else:
                        s+= end
                        return s
                else:
                    s += end
                    return s

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

21890
来自专栏zhisheng

SimpleDateFormat 如何安全的使用?

看到这条我立马就想起了我实习的时候有个项目里面就犯了这个错误,记得当时是这样写的:

11110
来自专栏趣学算法

数据结构 第12讲 二叉树的层次遍历

二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示:

12330
来自专栏尾尾部落

[剑指offer] 按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

9520
来自专栏大闲人柴毛毛

剑指offer代码分析——面试题13在O(1)内删除链表结点

本题详细解析都已在代码中注释了: /** * 给一个单链表,头指针为first,请用O(1)时间删除其中节点p * @author chibozhou *...

38250
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

9840
来自专栏日常分享

通过BitSet完成对单词使用字母的统计

  BitSet类实现了一组位或标记(flag),这些位可被分别设置或清除。当需要跟踪一组布尔值时,这种类很有用。

12220
来自专栏灯塔大数据

每周学点大数据 | No.25二叉搜索树回顾(二)

No.25期 二叉搜索树回顾(二) Mr. 王:既然提到了有序的状态,那么我们就来谈谈有根树的遍历问题。 小可:我知道,遍历就是访问一个数据集合中的所...

35560
来自专栏程序生活

Leetcode-Easy 543. Diameter of Binary Tree

543. Diameter of Binary Tree 描述: 求二叉树最长路径长度 ? 思路: 深度优先搜索 代码 # Definit...

32540
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

32660

扫码关注云+社区

领取腾讯云代金券