【Leetcode -563.二叉树的坡度 - Nowcoder -KY11.二叉树遍历】

		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;
		}

		#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;
		}