【LeetCode】1022. 从根到叶的二进制数之和、563. 二叉树的坡度

淡淡的烟草味﹌ 2024-03-25 20:47 60阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

## 1022. 从根到叶的二进制数之和 ##

[1022. 从根到叶的二进制数之和][1022.]

题目描述：

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。  
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

示例：

![8bd7ebd90e074c1abe3a96ae9b59347e.png][]

代码：

int RootLeaf(struct TreeNode* root,int n)
    {
        if(root==NULL)
        return 0;
        n=(n<<1)|root->val;
        if(root->left==NULL&&root->right==NULL)
        return n;
        return RootLeaf(root->left,n)+RootLeaf(root->right,n);
    
    }
    int sumRootToLeaf(struct TreeNode* root){
        return RootLeaf(root,0);
    }

## 563. 二叉树的坡度 ##

[563. 二叉树的坡度][563.]

题目描述：

给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。

一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。

整个树 的坡度就是其所有节点的坡度之和。

示例：

![88623c16026d416694a56400a4b75216.png][]

![111d280f04e54e0f8967583f735f01be.png][]

![c695277afd9c42a6824c20dcdf86aa9b.png][]

思路：

用leftnum和rightnum分别记录root左右子树所有节点的数之和

通过dfs函数不断递归出每个节点的左右子树，num传地址调用记录出所有的坡度和

代码：

int dfs(struct TreeNode*root, int* num)
    {
        if(root==NULL)
        return 0;
        int leftnum=dfs(root->left,num);
        int rightnum=dfs(root->right,num);
        int ret=0;
        ret+=leftnum+rightnum+root->val;
        *num+=abs(leftnum-rightnum);
        return ret;
    }
    int findTilt(struct TreeNode* root){
        //leftnum记录左子树所有的节点的值总和
        //rightnum记录右子树所有节点的值总和
        //num记录坡度和
        //ret记录各个位置的坡度
        if(root==NULL)
        return 0;
        int num=0;
        dfs(root,&num);
        return num;
    }

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/190ee3d1e8dd47cc9f38375f53010e37.png
[1022.]: https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
[8bd7ebd90e074c1abe3a96ae9b59347e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/edd1fac9846a4c3695439a18d6a2c6f7.png
[563.]: https://leetcode.cn/problems/binary-tree-tilt/
[88623c16026d416694a56400a4b75216.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/afa8104f9be742568654013112fb54f3.png
[111d280f04e54e0f8967583f735f01be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1a0957a109fe4ed585d4b72f8eea8286.png
[c695277afd9c42a6824c20dcdf86aa9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/705bddfe332c454eb793c42139648298.png