二叉树的最大宽度

原始地址:

博客花园:二叉树的最大宽度

CSDN:二叉树的最大宽度序列

标题描述

给你一个二叉树的根节点root,返回树的最大宽度,

树的最大宽度是所有层的最大宽度,

每层的宽度被定义为该层最左边和最右边的非空节点之间的长度,

这个二叉树被认为是和全二叉树一样的结构,在两个端点之间会有一些空节点延伸到这一层,这些空节点也被包含在长度中。

主要思路

两个数据项被添加到该数据结构中:

对于一棵全二叉树,如果当前节点是depth,pos,那么它的左子节点是,合适的孩子是,

参照二叉树的层遍历遍历二叉树,并开始在下一层结算上一层的结果。

而且每次要记录上一层最左边的位置,在右层的末尾,记录一个最右边的位置,然后留下一个全局最大max。max的更新策略是

查看完整代码。

标题描述

二叉树的最大宽度

给定一棵二叉树,你需要写一个函数来得到树的最大宽度。二叉树的最大宽度指的是具有最大节点数的层中的节点数。

有关链接,请参见:二叉树的最大宽度

与上一个问题不同的是,这个问题的最大宽度是有效节点的个数,所以不包括空节点。

主要思路

可以使用哈希表,按照层次遍历的方法存储每层的节点数。但是,有一种更节省空间的方法可以设置有限数量的变量,而无需申请哈希表。

然后,对二叉树进行分层遍历。在遍历过程中,如果遍历到的当前节点C满足要求,即当前节点是当前结束位置的节点,则可以确定一层的结束,可以更新全局max,当前层的节点数为零,即可以将较低端的节点赋给,

查看完整代码。

算法和数据结构笔记

发表评论

Copyright 2002-2022 by 琮莫零食网(琼ICP备2022001899号-3).All Rights Reserved.