二叉树坡度递归c代码
时间: 2024-05-10 18:12:02 浏览: 4
二叉树的坡度是指二叉树的所有结点左子树结点之和与右子树结点之和的差的绝对值之和。以下是一个递归实现二叉树坡度的C代码:
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int tilt(struct TreeNode* root) {
if (!root) return 0; // 如果为空,返回0
int left = sum(root->left); // 计算左子树结点之和
int right = sum(root->right); // 计算右子树结点之和
return abs(left - right) + tilt(root->left) + tilt(root->right); // 递归计算左右子树的坡度之和
}
int sum(struct TreeNode* node) {
if (!node) return 0; // 如果为空,返回0
return node->val + sum(node->left) + sum(node->right); // 递归计算子树结点之和
}
```
相关问题
二叉树非递归c语言代码
二叉树的非递归遍历可以使用栈来实现。以下是二叉树的非递归遍历的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点的定义
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 栈结点的定义
struct StackNode {
struct TreeNode* node;
struct StackNode* next;
};
// 入栈操作
void push(struct StackNode** top, struct TreeNode* node) {
struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
stackNode->node = node;
stackNode->next = *top;
*top = stackNode;
}
// 出栈操作
struct TreeNode* pop(struct StackNode** top) {
if (*top == NULL) {
return NULL;
}
struct TreeNode* node = (*top)->node;
struct StackNode* temp = *top;
*top = (*top)->next;
free(temp);
return node;
}
// 非递归前序遍历
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct StackNode* stack = NULL;
push(&stack, root);
while (stack != NULL) {
struct TreeNode* node = pop(&stack);
printf("%d ", node->val);
if (node->right != NULL) {
push(&stack, node->right);
}
if (node->left != NULL) {
push(&stack, node->left);
}
}
}
// 非递归中序遍历
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct StackNode* stack = NULL;
struct TreeNode* current = root;
while (current != NULL || stack != NULL) {
while (current != NULL) {
push(&stack, current);
current = current->left;
}
current = pop(&stack);
printf("%d ", current->val);
current = current->right;
}
}
// 非递归后序遍历
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct StackNode* stack1 = NULL;
struct StackNode* stack2 = NULL;
push(&stack1, root);
while (stack1 != NULL) {
struct TreeNode* node = pop(&stack1);
push(&stack2, node);
if (node->left != NULL) {
push(&stack1, node->left);
}
if (node->right != NULL) {
push(&stack1, node->right);
}
}
while (stack2 != NULL) {
struct TreeNode* node = pop(&stack2);
printf("%d ", node->val);
}
}
// 创建二叉树结点
struct TreeNode* createNode(int val) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
// 创建二叉树
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
// 非递归前序遍历
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\n");
// 非递归中序遍历
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
// 非递归后序遍历
printf("Postorder traversal: ");
postorderTraversal(root);
printf("\n");
return 0;
}
```
二叉树坡度递归计算动图
二叉树的坡度是指二叉树中所有节点的左子树节点之和与右子树节点之和的差的绝对值之和。如果一个二叉树为空,那么它的坡度为0。
计算二叉树的坡度,可以采用递归的方式。对于每个节点,我们可以计算其左右子树节点之和,并求出左右子树节点之和的差的绝对值。然后将左右子树节点之和的差的绝对值累加到一个全局变量中,最终得到二叉树的坡度。
下面是一个二叉树坡度递归计算的动图:
![image.png](https://cdn.nlark.com/yuque/0/2021/png/219901/1628709154206-8b3cda5d-090c-452d-a4ba-1dbf02a7e4c9.png#clientId=u7c6c2d57-5986-4&from=paste&height=422&id=u3a9a2f58&name=image.png&originHeight=422&originWidth=572&originalType=binary&ratio=1.00&size=32279&status=done&style=none&taskId=u2f7a5118-49b8-4372-ba26-45c89d7c835&width=572)