题目:给你一个二叉树的根节点 root ,计算并返回 整个树 的坡度 。 一个树的 节点的坡度 定义即为,该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话,左子树的节点之和为 0 ;没有右子树的话也是一样。空结点的坡度是 0 。 整个树 的坡度就是其所有节点的坡度之和。
示例 1:
输入:root = [1, 2, 3] 输出:1 解释: 节点 2 的坡度: | 0 - 0 | = 0(没有子节点) 节点 3 的坡度: | 0 - 0 | = 0(没有子节点) 节点 1 的坡度: | 2 - 3 | = 1(左子树就是左子节点,所以和是 2 ;右子树就是右子节点,所以和是 3 ) 坡度总和:0 + 0 + 1 = 1
示例 2:
输入:root = [4, 2, 9, 3, 5, null, 7] 输出:15 解释: 节点 3 的坡度: | 0 - 0 | = 0(没有子节点) 节点 5 的坡度: | 0 - 0 | = 0(没有子节点) 节点 7 的坡度: | 0 - 0 | = 0(没有子节点) 节点 2 的坡度: | 3 - 5 | = 2(左子树就是左子节点,所以和是 3 ;右子树就是右子节点,所以和是 5 ) 节点 9 的坡度: | 0 - 7 | = 7(没有左子树,所以和是 0 ;右子树正好是右子节点,所以和是 7 ) 节点 4 的坡度: | (3 + 5 + 2) - (9 + 7) | = | 10 - 16 | = 6(左子树值为 3、5 和 2 ,和是 10 ;右子树值为 9 和 7 ,和是 16 ) 坡度总和:0 + 0 + 0 + 2 + 7 + 6 = 15
示例 3:
输入:root = [21, 7, 14, 1, 1, 2, 2, 3, 3] 输出:9
提示: 树中节点数目的范围在[0, 10^4] 内
思路:化为子问题用变量 ans 记录左子树和右子树每个节点的坡度;结束条件,如果为空,就返回0;如果不为空,就继续递归其左子树和右子树,计算其左子树与右子树的和;如果不为空,返回其左子树或右子树的和;
int dfs(struct TreeNode* root, int* ans)
{
if (root == NULL)
return 0;
//左右子树节点
int leftTree = dfs(root->left, ans);
int rightTree = dfs(root->right, ans);
//该节点的坡度
*ans += abs(leftTree - rightTree);
//返回左右子树的和,和该根的 val
return leftTree + rightTree + root->val;
}
int findTilt(struct TreeNode* root)
{
// ans 记录二叉树的坡度
int ans = 0;
dfs(root, &ans);
return ans;
}
题目:编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。 建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
输入描述: 输入包括1行字符串,长度不超过100。 输出描述: 可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。
示例1 输入: abc##de#g##f###
输出: c b e g d f a
思路:因为字符串是按照前序遍历得到的,所以我们也按照先创建根的节点,再创建其左右子树的节点,最后将它们连接起来;最后创建完二叉树后,按照中序遍历打印数据;
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef char BTDataType;
//节点的结构体
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;
//创建新的节点
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
assert(newnode);
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
//创建二叉树
BTNode* CreatTree(BTDataType* a, int* pi)
{
//如果是 # ,就返回空
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//如果不为空,就创建该字符的节点,pi往后遍历后面的字符
BTNode* root = BuyNode(a[(*pi)++]);
//将节点的左右子树连接起来
root->left = CreatTree(a, pi);
root->right = CreatTree(a, pi);
//返回根
return root;
}
//打印中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
return;
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
int main()
{
char a[100];
scanf("%s", &a);
int i = 0;
//i遍历字符串
BTNode* root = CreatTree(a, &i);
InOrder(root);
return 0;
}