专栏首页架构说958. 二叉树的完全性检验

958. 二叉树的完全性检验

早安心语

听到别人生活不如意,就自我感觉良好;

见到他人晒幸福晒成绩,又觉得自己失败迷茫。

把时间都用来关注别人,哪还有功夫提升自己?

记住,你的注意力在哪里,成长就在哪里。

向着自己心中的愿景勇敢前进,踏实走好每一步,终有一天生活会垂青于你。

958. 二叉树的完全性检验

一、描述

给定一个二叉树,确定它是否是一个完全二叉树

思考 60秒 。。。

思考 60秒 。。

这个题目从画图开始。

算法五个重要的特征:

  • 输入项,输出项(题目已经给了)
  • 可行性(复杂问题转化成熟悉子问题)
  • 有穷性(在算法描述体现)
  • 确切性(在算法描述体现)

二、思路

  • 逻辑视图

输入:[1,2,3,4,5,null,7] 输出:false 解释:值为 7 的结点没有尽可能靠向左侧

熟悉子问题

  • 我第一眼就看出 上面例子更不是完全二叉树,5和7之间 存在null?但是无法用程序语言描述出?【如何全部遍历】
  • 根据观察 层次遍历,遇到null,后面还有记录,不对了,设立flag, 如果队还有记录,在遇到有记录的肯定不对。【有遗漏不对】
  • 从物理视图变成逻辑视图,完全利用满二叉树性质,想想堆排序。关键是怎么判断呢? 假如完全二叉树,7的编号就是7没有问题,

编号是7,tree的中长度为7。

  • 不是完全二叉树的编号也是7,总长度是6。

这样做那里不对?

  • bug1 我们只需要检查最后一个编号是否正确,因为最后一个编号的值最大。

这样能够做2×index会越界。

  • 为什么不能直接通过一个节点 left 不存在,right存在来判断 这样不是更直接吗?好像这样理论上没有问题。

从节点2从单个角度看,是合法的,不能保证整个tree都是合法的。

算法描述:

  1. 计算tree的高度
  2. dfs遍历tree。如果index >count fasle

2个递归,浪费空间还是挺大的。

三、代码

  • 测试bug,全部遍历完毕。2×i 超过整数范围。这个没考虑tree的最大长度。[全部遍历在判断会越界]
  • 放轻松,虽然是c++实现,拒绝奇技淫巧,通俗易懂。
class Solution {public:bool isCompleteTree(TreeNode root) {
int count =getNode(root); 

return isCompleteTree(root,1,count);


return isCompleteTree(root->left) &&  isCompleteTree(root->right);
}

bool isCompleteTree(TreeNode* root,int index,int &count)
{
    if (NULL == root)
    {
        return true;
    }
    if(index > count)
    {
      return false;
    }

    return isCompleteTree(root->left,2*index,count) && isCompleteTree(root->right,2*index+1,count);
}

int getNode(TreeNode* root)
{
   if ( root ==NULL)
   {
       return 0;
   }

   return getNode(root->left) + getNode(root->right) +1;
}
  • golang
/**958. Check Completeness of a Binary Tree
Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
} */ func isCompleteTree(root *TreeNode) bool { if root == nil { return true } total := getNodes(root)


return isCompleteTreeByIndex(root, 1, total)

}
func getNodes(root *TreeNode) int {
if root == nil {
    return 0
}

return 1 + getNodes(root.Left) + getNodes(root.Right)
}
func isCompleteTreeByIndex(root *TreeNode, index int, total int) bool {
if nil == root {
return true
}
if index > total {
    return false
}

return isCompleteTreeByIndex(root.Left, 2*index, total) && isCompleteTreeByIndex(root.Right, 2*index+1, total)
}

分享最实用的经验 , 希望每一位来访的朋友都能有所收获! 如果有疑问请联系我,一起探讨,进步。

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-08

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单链表中头节点作用(深入理解)

    今天QQ群里有人咨询一个问题 例如单链表中头节点作用 然后联想到做项目中解决core一个问题 虽然每天都在吃饭睡觉打豆豆,啥框架业务都不懂 解决了这一个...

    程序员小王
  • leetcode第 132 场周赛

    时间复杂度:O(n^2) 有那个N个元素,每个元素计算N次。 空间复杂度:O(n)

    程序员小王
  • leetcode每日一题-99. 恢复二叉搜索树

    程序员小王
  • 【leetcode刷题】T112-验证二叉搜索树

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

    木又AI帮
  • Golang Leetcode 235. Lowest Common Ancestor of a Binary Search Tree.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89043473

    anakinsun
  • linux基础命令介绍三:文件搜索及其它

    find是一个非常有效的工具,它可以遍历目标目录甚至整个文件系统来查找某些文件或目录:

    用户5030870
  • LeetCode 337. 打家劫舍 III(记忆化+递归)

    在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子...

    Michael阿明
  • 如何使用CP / SCP / RSYNC在Linux中排除特定目录?

    对于任何系统管理员或一般Linux操作系统用户而言,在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时,由于某些特定原因,我们可...

    用户6543014
  • LeetCode 114. 二叉树展开为链表(递归)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-link...

    Michael阿明
  • BST & AVL 二分搜索树 & 平衡二叉树的实现原理

    本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

    大学里的混子

扫码关注云+社区

领取腾讯云代金券