L*********g
发帖数: 8 | 1 先是问了一些概念题，然后还剩30分钟：写个函数判断二叉树是完全二叉树
complete tree
例如
是：
a
/
b c
/ /
d e f g
/
h i
是：
a
/
b c
/ /
d e f g
/ /
h ij
不是：
a
/
b c
/ /
d e f g
/
h i j
不是：
a
/
b c
/
d e g
/
h i
只记得完全二叉树用在堆排序中。吭哧半天，想出了个算法能实现：只能按层遍历（看
下面的三步）。但到最后没时间了，代码没写出来，所以挂面了。
大致思路，分3步：
1.假设给定的树是complete binary tree,找出树的最大深度 = D：那么最左边的叶子
节点深度是树的最大深度。 从根（Level = 0）循环找到最左的叶子节点深度 = D。O(
log n)
2.找出倒数第二层，第D-1层节点：post-order递归遍历树，递归遍历时可以得到每个
节点的深度，如果是D-1层节点, 按从左到右的顺序存下来(递归能保证节点左到右顺序
，需要额外的空间 O(n))。判断D-1层是否满树，即，第D-1层有 2的D-1次方个节点。
否则就不是complete b tree. O(n)
3.从左到右依次处理存下的第D-1层节点，假定这是完全二叉树：(A)每个D-1层节点不
能有孙子，(B)第D-1层节点的孩子（D层，先左后右）一开始是满的，一旦没有，就全
为null。 O(n)
总的复杂度 = O(n)。请教各位大牛拍更好的算法。 |
s**x
发帖数: 7506 | 2 查了半天，都是利用 level order traversal 的。 |
f********e
发帖数: 91 | 3 应该可以用层次变例来做 只有最底层的所有节点没有子节点。。。
【在 L*********g 的大作中提到】
: 先是问了一些概念题，然后还剩30分钟：写个函数判断二叉树是完全二叉树
: complete tree
: 例如
: 是：
: a
: /
: b c
: / /
: d e f g
: /
|
b*******e
发帖数: 123 | 4 多谢分享。。
这个能不能是tree level traversal, 每次recursione的时候加个记号。
level 0 是0
下一个level的时候左边 (lastindex << 1)+0
右边(lastindex <<1) + 1
然后比较在推入层vector时候的index和这个是不是相符。不相符就不是。
遍历完了在数除了最后一层，每层个数是不是2^n |
b*****c
发帖数: 1103 | |
L*********g
发帖数: 8 | 6 Write a function to validate a complete binary tree. That is, the function
will take a binary tree as an input argument and return true if the given
binary tree is a complete binary tree.
A binary tree is complete if all levels except possibly the last are
completely full, and the last level has all its node to the left side.
For example, the following is a complete binary tree:
a
/ \
b c
/
d
The followings are not complete binary trees:
a
/ \
b c
/ \
d e
a
/ \
b c
/ / \
f d e |
l******6
发帖数: 340 | 7 level order traverse.
一个flag ： noMoreNode == false
过程中：
noMoreNode == false 的时候
如果一个节点左右child 都有， 正常继续 traverse, 左右child 先后进queue
如果一个节点只有左child/没有child, 左child 进queue/什么不干， noMoreNode =
true;
如果一个节点只有右child return false
当 noMoreNode == true的时候， 任何node需要进queue: return false
最后什么也没发生 return true |
c*******2
发帖数: 60 | 8 不知这个可以不...
boolean isCompleteBT(TreeNode root, int leftDepth, int rightDepth){
if(root == null) return true;
if(leftDepth < rightDepth || leftDepth > rightDepth + 1) return false;
TreeNode lNode = root.left, rNode = root.right;
int r = 0, l = 0;
while(lNode != null){
lNode = lNode.right;
r++;
}
while(rNode != null){
rNode = rNode.left;
l++;
}
if(r < l) return false;
return isCompleteBT(root.left, leftDepth-1, r) && isCompleteBT(root.
right, l, rightDepth-1);
} |
|
z****s
发帖数: 409 | 9 dfs(左子树)；//k=左子树深度。
if (左子树是满二叉树) {
dfs(右子树）；
return 右子树是否是深度为k-1的满二叉树，或深度为k的完全二叉树；
} esle if (左子树不是满二叉树，但是完全二叉树） {
dfs(右子树）；
return 右子树是否是深度为k-1的满二叉树；
} else return false；
包子拿来吧。 |
L*********g
发帖数: 8 | 10 感觉这个是标准答案。优雅，O(n)，代码最少。
=
【在 l******6 的大作中提到】
: level order traverse.
: 一个flag ： noMoreNode == false
: 过程中：
: noMoreNode == false 的时候
: 如果一个节点左右child 都有， 正常继续 traverse, 左右child 先后进queue
: 如果一个节点只有左child/没有child, 左child 进queue/什么不干， noMoreNode =
: true;
: 如果一个节点只有右child return false
: 当 noMoreNode == true的时候， 任何node需要进queue: return false
: 最后什么也没发生 return true
|
|
|
L*********g
发帖数: 8 | 11 leftDepth, rightDepth初始化值从哪里来？
对于这样的树，不是complete tree, 但返回结果是true吧.
N
N N
N N
【在 c*******2 的大作中提到】
: 不知这个可以不...
: boolean isCompleteBT(TreeNode root, int leftDepth, int rightDepth){
: if(root == null) return true;
: if(leftDepth < rightDepth || leftDepth > rightDepth + 1) return false;
: TreeNode lNode = root.left, rNode = root.right;
: int r = 0, l = 0;
: while(lNode != null){
: lNode = lNode.right;
: r++;
: }
|
c*******2
发帖数: 60 | 12 leftDepth是root往左走到黑, rightDepth是往右走到黑.
你这个例子里, 左子节点的rightDepth小于右子节点的leftDepth, 所以返回false.
if(r < l) return false;
【在 L*********g 的大作中提到】
: leftDepth, rightDepth初始化值从哪里来？
: 对于这样的树，不是complete tree, 但返回结果是true吧.
: N
: N N
: N N
|
g*********e
发帖数: 14401 | 13 做level order traversal
当第一次碰到某个node的任何一个child是NULL之后，
if
余下的所有node的所有children都是NULL
then
isComplete tree |
k******4
发帖数: 94 | 14 level order的最大问题就是空间复杂度，指数增长.
试着用DFS写了下，空间复杂度是O(logn)，时间O(n),
//treeDepth 是树的实际高度，desiredDepth是叶子的期望高度。
//当第一次遇到一个比treeDepth高度小一的叶子，把desiredDepth的设置为treeDepth
-1,并且需要后面所有叶子的高度都是这个值。
bool validateCompleteBT(TreeNode*root, const int &treeDepth, int &
desiredDepth, int curDepth, bool &setDesiredDepthFlag)
{
curDepth++;
if(root->left == NULL && root->right == NULL)
{
if(setDesiredDepthFlag && curDepth == (treeDepth-1))
{
setDesiredDepthFlag =false;
desiredDepth = treeDepth -1;
｝
return curDepth == desiredDepth;
}
return validateCompleteBT(root->left, treeDepth, desiredDepth,
curDepth,setDesiredDepthFlag )
&&validateCompleteBT(root->right, treeDepth, desiredDepth, curDepth,
setDesiredDepthFlag );
}
bool isCompleteBT(TreeNode *root)
{
int depth = 0;
TreeNode *curNode = root;
while(curNode != NULL)
{
curNode = curNode->left;
depth++;
}
if(depth <=1)
return true;
int desiredDepth = depth;
return validateCompleteBT(root, depth, desiredDepth, 0,true);
} |
z****s
发帖数: 409 | |
b***e
发帖数: 1419 | 16 1. Compute the height of each tree node. The height of a node is max(left.
heigth, right.height) + 1.
2. Compute the co-height of each tree node. The co-height of a node is min(
left.coHeight, right.coHeight) + 1.
3. A tree is complete if for every node:
left.coHeight >= right.height && left.height <= right.coHeight + 1
【在 L*********g 的大作中提到】
: 先是问了一些概念题，然后还剩30分钟：写个函数判断二叉树是完全二叉树
: complete tree
: 例如
: 是：
: a
: /
: b c
: / /
: d e f g
: /
|
j*********6
发帖数: 407 | 17 你这个 第一步 好像要分别考虑
left == null && right != null => return false;
left != null && right == null => nomorechildren = true
【在 g*********e 的大作中提到】
: 做level order traversal
: 当第一次碰到某个node的任何一个child是NULL之后，
: if
: 余下的所有node的所有children都是NULL
: then
: isComplete tree
|
j*********6
发帖数: 407 | 18 为什么level traverse 的 space cost 是指数级别的呢？ 不就是O(n) 吗？ 而且
level traverse的 时间复杂度 在 树的高度很高的时候 是很有优势的
个人愚见
treeDepth
【在 k******4 的大作中提到】
: level order的最大问题就是空间复杂度，指数增长.
: 试着用DFS写了下，空间复杂度是O(logn)，时间O(n),
: //treeDepth 是树的实际高度，desiredDepth是叶子的期望高度。
: //当第一次遇到一个比treeDepth高度小一的叶子，把desiredDepth的设置为treeDepth
: -1,并且需要后面所有叶子的高度都是这个值。
: bool validateCompleteBT(TreeNode*root, const int &treeDepth, int &
: desiredDepth, int curDepth, bool &setDesiredDepthFlag)
: {
: curDepth++;
: if(root->left == NULL && root->right == NULL)
|
