二叉树算法

面试中的二叉树

二叉树的节点总数

1
2
3
4
5
6
int nodeNumber(struct node *root) {
if (root == NULL) {
return 0;
}
return nodeNumber(root->left) + nodeNumber(root->right) + 1;
}

二叉树的深度

1
2
3
4
5
6
7
8
9
// 二叉树的深度
int nodeDepth(struct node *root) {
if (root == NULL) {
return 0;
}
return nodeDepth(root->left) > nodeDepth(root->right)
? nodeDepth(root->left) + 1
: nodeDepth(root->right) + 1 ;
}

叶结点总数

1
2
3
4
5
6
7
8
9
10
//叶子结点的个数
int leafNode(struct node *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return leafNode(root->left) + leafNode(root->right);
}

第k层的结点数

1
2
3
4
5
6
7
8
9
10
//第k层的结点数
int kNode(struct node *root, int k, int level = 1) {
if (root == NULL) {
return 0;
}
if (k == level) {
return 1;
}
return kNode(root->left, k, level + 1) + kNode(root->right, k, level + 1);
}

判断二叉树是不是平衡二叉树

1
2
3
4
5
6
7
8
9
10
//判断二叉树是不是平衡二叉树【左子树与右子树高度差不大于1】
int isAVL(struct node * root) {
if (root == NULL) {
return 0;
}
// 利用树的深度
int leftDepth = nodeDepth(root->left);
int rightDepth = nodeDepth(root->right);
return abs(leftDepth - rightDepth) > 1 ? 1 : 0;
}
xpisme wechat
微信号