CCI题目4-1:Check Balance of a Binary Tree,二叉树的基本算法

By | 2012 年 11 月 22 日

这里我把题目理解为,任意两个叶子节点(左右子树都空)的深度不超过1.
那就计算一下一棵树的叶子节点中最大的深度和最小的深度,两者不超过1即可。

PS.但是按照书上的solution,代码翻译出来的题意,对于叶子节点的理解是说Null节点。



代码中还包含了这一部分的一些基本代码,包括:
1.从string初始化一棵树(借鉴leetcode的表示方法)
2.递归实现的inorder,preorder,postorder深度优先遍历
3.queue实现的广度优先遍历



题目
Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.



Code

<

pre>
//
// main.cpp
// CCI.4.1.Check Balance of a Tree
//
// Created by Qiu Xiangyu on 12-11-21.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;

struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int val, TreeNode *l, TreeNode *r) {
value = val;
left = l;
right = r;
}
TreeNode(int val = 0) {
value = val;
left = NULL;
right = NULL;
}
};

TreeNode *buildTreeFromString(string s) {
if (s.size() == 0 || s[0] == ‘#’) {
return NULL;
}
TreeNode *root = NULL;
queue<TreeNode**> que;
que.push(&root);
int v = 0;
bool isnull = false;
int istr = 0;
while (true) {
if (istr >= s.size() || s[istr] == ‘,’) {

        TreeNode **ppnode = que.front();
        que.pop();

        if (ppnode && !isnull) {
            TreeNode *newNode = new TreeNode(v);
            *ppnode = newNode;
            que.push(&newNode->left);
            que.push(&newNode->right);
        } else {
            que.push(NULL);
            que.push(NULL);
        }

        if (istr >= s.size()) {
            break;
        }

        v = 0;
    } else {
        if (s[istr] == '#') {
            v = 0;
            isnull = true;
        } else {
            v = 10 * v + s[istr] - '0';
            isnull = false;
        }
    }
    ++istr;
}
return root;

}

void inorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
inorder(root->left, nodeHandler);
nodeHandler(root);
inorder(root->right, nodeHandler);
}

void preorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
nodeHandler(root);
preorder(root->left, nodeHandler);
preorder(root->right, nodeHandler);
}

void postorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
postorder(root->left, nodeHandler);
postorder(root->right, nodeHandler);
nodeHandler(root);
}

void breadthfirst(TreeNode root, void (nodeHandler)(TreeNode* node)) {
queue<TreeNode*> que;
que.push(root);
int count = root ? 1 : 0;
while (que.size()) {
TreeNode *node = que.front();
que.pop();
if (node) {
–count;
nodeHandler(node);
que.push(node->left);
que.push(node->right);
if (node->left) {
++count;
}
if (node->right) {
++count;
}
} else {
cout<<“n\n”;
que.push(NULL);
que.push(NULL);
}
if (0 == count) {
break;
}
}
}

void printNode(TreeNode *node) {
cout<value<<endl;
}

int mindepth(TreeNode *node) {
if (NULL == node) {
return 0;
}
int rightMin = mindepth(node->right);
if (node->left) {
int leftMin = mindepth(node->left);
if (node->right) {
return 1 + (leftMin < rightMin ? leftMin : rightMin);
} else {
return 1 + leftMin;
}
} else {
return 1 + rightMin;
}
}
int maxdepth(TreeNode *node) {
if (NULL == node) {
return 0;
}
int leftmax = maxdepth(node->left);
int rightmax = maxdepth(node->right);
return 1 + (leftmax > rightmax ? leftmax : rightmax);
}
bool isBalance(TreeNode *root) {
int dmax = maxdepth(root);
int dmin = mindepth(root);
return abs(dmax – dmin) <= 1;
}
int main(int argc, const char * argv[])
{
// insert code here…
std::cout << “Hello, World!\n”;
string instr = “1,2,3,4,#,#,#,5”;
TreeNode *root = buildTreeFromString(instr);
breadthfirst(root, printNode);
int dmax = maxdepth(root);
int dmin = mindepth(root);
cout<<“dmax:”<<dmax<<“,dmin:”<<dmin<<endl;
cout<<“Is balance:”<<isBalance(root)<<endl;
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注