d********w
发帖数: 363 | 1 complete tree定义
a binary tree in which every level, except possibly the last, is completely
filled, and all nodes are as far left as possible.
不能使用额外的空间，
insert(int data, TreeNode root)
例如complete tree
1
2 3
4
插入节点就是成为２的右儿子
1
2 3
4 5 | I*******l
发帖数: 203 | 2 Update: fix some boundary condition checks
recursively call a function Node* cc(Node* root) to find out where to insert an extra node, where cc checks left subtree first and then right subtree to find a non-full subtree. It returns NULL if both subtrees are full.
Node* cc(Node* root)
{ // make sure that leaf node return NULL
if (root == NULL)
return NULL;
// first check if root has both children, if not return root
if (root->left != NULL && root->right == NULL)
return root;
Node* tmp = cc(root->left);
// left subtree has priority
if (tmp != NULL)
return tmp;
tmp = cc(root->right);
// if right subtree is also full, then return NULL
return tmp ? tmp : NULL;
} | p*****2
发帖数: 21240 | | h****e
发帖数: 928 | 4 难点是不能使用额外的空间。BFS要用一个队列吧。
【在 p*****2 的大作中提到】
: BFS就可以了。
| p*****2
发帖数: 21240 | 5
sorry. in place呀。
【在 h****e 的大作中提到】
: 难点是不能使用额外的空间。BFS要用一个队列吧。
| t**********h
发帖数: 2273 | 6 有nullpointer的异常。每次调用的时候检查一下，或者第一行先判断root是否为空
很不错的想法。如果已经是完全树，则跑到最左下角节点去insert
insert an extra node, where cc checks left subtree first and then right
subtree to find a non-full subtree. It returns NULL if both subtrees are
full.
【在 I*******l 的大作中提到】
: Update: fix some boundary condition checks
: recursively call a function Node* cc(Node* root) to find out where to insert an extra node, where cc checks left subtree first and then right subtree to find a non-full subtree. It returns NULL if both subtrees are full.
: Node* cc(Node* root)
: { // make sure that leaf node return NULL
: if (root == NULL)
: return NULL;
: // first check if root has both children, if not return root
: if (root->left != NULL && root->right == NULL)
: return root;
: Node* tmp = cc(root->left);
| p*****2
发帖数: 21240 | 7 traverse一下吧。如果都满了就插到最左边的叶子下边。 | t**********h
发帖数: 2273 | 8 后续遍历，同时统计左右子树的节点数目，第一个左右节点数不相同的及是要找的子树根节点。前提
是假定
了这棵树是完整树。
Node result = null;
boolean setResult = true;
int check(Node node){
if(node == null){
return 0;
}
int left = check(node.left);
int right = check(node.right);
if(left != right && setResult){
result = node;
setResult = false;
}
return left + right + 1;
}
补充一下，在check弄完之后，result有两种情况
1.result为空，那么这棵树最底层也被填满，那么下一步找到最左下角叶子插入一个左节点
2.result不为空，那么这棵树最底层没有被填满，那么其倒数二层肯定是被填满的。result就是第
一个左右子树节点数目不同的节点，那么找到result的右子树的最左下角的那个点(要判断
result.right非空，如果空，直接擦），就肯定是要插入的点 | j********e
发帖数: 1192 | 9 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
类似于binary search的算法，测试代码也在下面，应该没有大bug。
先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
#include
#include
#include
#include
using namespace std;
class Node {
private:
Node *left;
Node *right;
int value;
public:
Node() {
left = right = NULL;
value = 0;
}
Node(int v) {
left = right = NULL;
value = v;
}
int Height(Node *node) {
int h = 0;
if(node == NULL)
return 0;
while(node) {
h++;
node = node->left;
}
return h;
}
int HeightRight(Node *node) {
int h = 0;
if(node == NULL)
return 0;
while(node) {
h++;
node = node->right;
}
return h;
}
bool Insert(Node *root, Node *newNode) {
if(root == NULL)
return false;
int height = Height(root);
int checkLevel = 1;
// First check if last level is full
if(height == HeightRight(root)) {
Node *node = root;
while(node) {
if(node->left == NULL) {
node->left = newNode;
return true;
}
node = node->left;
}
}
Node *lastMoveLeftNode = root;
Node *tmp = root;
while(true) {
if(tmp->right) {
int h = Height(tmp->right) + checkLevel;
if(h == height) {
tmp = tmp->right;
checkLevel ++;
}
else {
lastMoveLeftNode = tmp;
tmp = tmp->left;
checkLevel ++;
}
}
else if(tmp->left) {
// tmp->left is the last node in the complete tree.
tmp->right = newNode;
return true;
}
else {
// tmp is the last node in the complete tree.
// So go back to lastMoveLeftNode to inert newNode
if(!lastMoveLeftNode->right) {
lastMoveLeftNode->right = newNode;
return true;
}
else {
tmp = lastMoveLeftNode->right;
while(tmp->left)
tmp = tmp->left;
tmp->left = newNode;
return true;
}
}
}
return false;
}
void Print() {
list queue;
queue.push_back(this);
while(queue.size()>0) {
Node *node = queue.front();
queue.pop_front();
printf("%d ", node->value);
/*
if(node->left) {
printf("(%d, ", node->left->value);
}
else
printf("(NULL, ");
if(node->right) {
printf("%d) ", node->right->value);
}
else
printf("NULL) ");
*/
if(node->left) {
queue.push_back(node->left);
if(node->right) {
queue.push_back(node->right);
}
}
}
printf("\n\n");
}
};
int main(int argc, char *argv[]) {
int n = 10;
if(argc >= 2) {
n = atoi(argv[1]);
}
Node *root = new Node(0);
for(int i=1; i
//printf("\nInsert %d\n", i);
root->Insert(root, new Node(i));
}
root->Print();
return 0;
}
入点。前提是假定
【在 t**********h 的大作中提到】
: 后续遍历，同时统计左右子树的节点数目，第一个左右节点数不相同的及是要找的子树根节点。前提
: 是假定
: 了这棵树是完整树。
: Node result = null;
: boolean setResult = true;
: int check(Node node){
: if(node == null){
: return 0;
: }
:
| D********g
发帖数: 650 | 10 不错的想法，不过这个算法只能handle下面这种case:
1
2 4
3
但是cc对下面的case会return NULL,但是我们希望cc return 4.
1
2 4
3 5
insert an extra node, where cc checks left subtree first and then right
subtree to find a non-full subtree. It returns NULL if both subtrees are
full.
【在 I*******l 的大作中提到】
: Update: fix some boundary condition checks
: recursively call a function Node* cc(Node* root) to find out where to insert an extra node, where cc checks left subtree first and then right subtree to find a non-full subtree. It returns NULL if both subtrees are full.
: Node* cc(Node* root)
: { // make sure that leaf node return NULL
: if (root == NULL)
: return NULL;
: // first check if root has both children, if not return root
: if (root->left != NULL && root->right == NULL)
: return root;
: Node* tmp = cc(root->left);
| c*****n
发帖数: 96 | 11 void getNode (Node *root, int level, int & minLevel, Node *&target){
if (root == NULL) return;
if (root->left == NULL || root->right == NULL){
if (level < minLevel){
target = root;
minLevel = level;
}
}
getNode(root->left, level+1, minLevel, target);
getNode(root->right, level+1, minLevel, target);
}
Node *target = NULL;
getNode(root, 0, INT_MAX, target) | c*****n
发帖数: 96 | 12 void getNode (Node *root, int level, int & minLevel, Node *&target){
if (root == NULL) return;
if (root->left == NULL || root->right == NULL){
if (level < minLevel){
target = root;
minLevel = level;
}
}
getNode(root->left, level+1, minLevel, target);
getNode(root->right, level+1, minLevel, target);
}
Node *target = NULL;
getNode(root, 0, INT_MAX, target) | t**********h
发帖数: 2273 | 13 这个算法好长啊，面试的时候能写完吗？
【在 j********e 的大作中提到】
: 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
: 类似于binary search的算法，测试代码也在下面，应该没有大bug。
: 先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
: 说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
: #include
: #include
: #include
: #include
: using namespace std;
: class Node {
| p*****o
发帖数: 1285 | 14 如果知道节点数，可以直接算出来位置。具体的，先遍历计数，O(n)，然后根据总数计
算到下一个节点的路径，可以用位操作很方便算出，然后再O(log n)跑到位置。总的是
O（n + log n)=O(n)。如果已知节点数就是O(log n)。
completely
【在 d********w 的大作中提到】
: complete tree定义
: a binary tree in which every level, except possibly the last, is completely
: filled, and all nodes are as far left as possible.
: 不能使用额外的空间，
: insert(int data, TreeNode root)
: 例如complete tree
: 1
: 2 3
: 4
: 插入节点就是成为２的右儿子
|
|
