[已解决]求从根节点到每一个叶子节点的路径的值的和

秋木叶 · 发表于 2019-3-18 15:07:27

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

例如
1
/ \
2 3

答案为 12 + 13 = 25

求C语言的完整代码，感谢感谢！

最佳答案

月排行榜 / 总排行榜

Croper

2019-3-18 18:00:15

struct treenode {
int val;
treenode* left;
treenode* right;
treenode(int n) :val(n),left(nullptr), right(nullptr) {};
};
int GetTreeSum_Loop(int a, treenode* node) {
if (node == nullptr) return 0;
a = a * 10 + node->val;
if (node->left == nullptr && node->right == nullptr) return a;
return GetTreeSum_Loop(a, node->left) + GetTreeSum_Loop(a, node->right);
}
int GetTreeSum(treenode* root) {
return GetTreeSum_Loop(0, root);
}

复制代码

跳转到最佳答案楼层

BngThea · 发表于 2019-3-18 16:06:06

直接百度

Croper · 发表于 2019-3-18 17:10:10

。。伸手也不是这么伸手的啊，
你要求代码，至少把输入格式写出来啊。。你这输入格式是什么。。。。图片么，那我真的不会。。

Croper · 发表于 2019-3-18 18:00:15

这个最佳答案由 Croper 给出，感谢 Croper 的回答。

单击隐藏图章

struct treenode {
int val;
treenode* left;
treenode* right;
treenode(int n) :val(n),left(nullptr), right(nullptr) {};
};
int GetTreeSum_Loop(int a, treenode* node) {
if (node == nullptr) return 0;
a = a * 10 + node->val;
if (node->left == nullptr && node->right == nullptr) return a;
return GetTreeSum_Loop(a, node->left) + GetTreeSum_Loop(a, node->right);
}
int GetTreeSum(treenode* root) {
return GetTreeSum_Loop(0, root);
}

复制代码

秋木叶 · 发表于 2019-3-19 16:21:25

本帖最后由秋木叶于 2019-3-19 16:23 编辑

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int ElemType;
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
typedef struct sqStack
{
ElemType *base;
ElemType *top; // 用于标注栈顶的位置
int stackSize;
}sqStack;
//全局栈
sqStack s;
//初始化栈
void initStack(sqStack *s)
{
s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
if( !s->base )
exit(0);
s->top = s->base; // 最开始，栈顶就是栈底
s->stackSize = STACK_INIT_SIZE;
}
//入栈
void Push(sqStack *s, ElemType e)
{
// 如果栈满，追加空间
if( s->base - s->top >= s->stackSize ) // 这个根据自己的编译器和系统，来决定 s->base - s->top 还是 s->top - s->base
{
s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base )
exit(0);
s->top = s->base + s->stackSize; // 设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT; // 设置栈的最大容量
}
*(s->top) = e;
s->top++;
}
//出栈
void Pop(sqStack *s, ElemType *e)
{
if( s->top == s->base ) // 栈已空空是也
return ;
*e = *--(s->top);
}
//判断栈是否空
int IsEmpty(sqStack *s){
if( s->top == s->base )
return 0;
else
return 1;
}
// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateBiTree(BiTree *T)
{
char c;
scanf("%c", &c);
if( '#' == c )
{
*T = NULL;
}
else
{
*T = (BiTNode *)malloc(sizeof(BiTNode));
(*T)->data = c;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
// 访问二叉树结点的具体操作，你想干嘛？！
void visit(char c, int level)
{
printf("%c 位于第 %d 层\n", c, level);
}
// 前序遍历二叉树
void PreOrderTraverse(BiTree T, int level)
{
if( T )
{
visit(T->data, level);
PreOrderTraverse(T->lchild, level+1);
PreOrderTraverse(T->rchild, level+1);
}
}
void AllPath(BiTree T,char path[],int pathLength)
{
if(T!=NULL)
{
if(T->lchild==NULL&&T->rchild==NULL)
{
path[pathLength]=T->data;
printf("根节点到%c叶子节点的路径为: ",T->data);
int xnum = 0;
for(int i=0;i<=pathLength;i++){
printf("%c ",path[i]);
xnum = path[i] - 48 + xnum * 10 ;// 将树中元素 char 转为 int
}
Push(&s, xnum);
//printf(" x=%d \n",xnum);
printf("\n");
}
else
{
path[pathLength++]=T->data;
AllPath(T->lchild,path,pathLength);
AllPath(T->rchild,path,pathLength);
pathLength--;
}
}
}
int main()
{
//int level = 1;
BiTree T = NULL;
int sum = 0,e;
initStack(&s);
char path[100];
int pathLength=0;
CreateBiTree(&T);
AllPath(T,path,pathLength);
//PreOrderTraverse(T, level);
while( IsEmpty(&s) ){
Pop(&s, &e);
//printf("sum = %d\n",sum);
sum += e;
}
printf("sum = %d\n",sum);
return 0;
}

复制代码

秋木叶 · 发表于 2019-3-19 16:25:53

Croper 发表于 2019-3-18 18:00

谢谢啦！我自己用本办法解决了

秋木叶 · 发表于 2019-3-19 16:27:16

Croper 发表于 2019-3-18 17:10
。。伸手也不是这么伸手的啊，
你要求代码，至少把输入格式写出来啊。。你这输入格式是什么。。。。图片么 ...

sorry，当时考官就是这么简洁的问我的

账号		自动登录	找回密码
密码			立即注册

[已解决]求从根节点到每一个叶子节点的路径的值的和

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块