刷题日记---二叉树递归专题

2025/5/10 7:54:04 来源：https://blog.csdn.net/2402_86037826/article/details/145620966 浏览: 次关键词：刷题日记---二叉树递归专题

文章目录

1. 从根到叶的二进制数之和
2. 二叉树的坡度
3. 总结

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

描述：
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
返回这些数字之和。题目数据保证答案是一个 32 位整数。

OJ链接

根结点到一个叶子结点为一条路径，有多少个叶子结点就有多少条路径，而此题要求的便是所有路径之和。

所以，二叉树的各个路径都必须遍历，所以需要递归二叉树，路径的遍历是向下的，因此是深度优先遍历，在遍历过程中，可以用一个变量累加每条路径之和。

具体代码如下：
class Solution {
public:int sum = 0;//用以记录路径之和void dfs(TreeNode* root,int val){if(root == nullptr)//如果是空，直接返回return;val = val * 2 + root->val;if(root->left == nullptr && root->right == nullptr)//判断是否到路径末尾，即叶子结点处{sum += val;//此时的val，即一条路径上的二进制数之和return;}//没有到路径末尾，因此继续向下递归dfs(root->left,val);dfs(root->right,val);}int sumRootToLeaf(TreeNode* root) {dfs(root,0);return sum;  }
};

2. 二叉树的坡度

描述：
给你一个二叉树的根节点 root ，计算并返回整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的节点之和和右子树节点之和的差的绝对值。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
整个树的坡度就是其所有节点的坡度之和。

OJ链接

在这道题中，结点坡度的定义与树的坡度的定义，二者是不同的。结点的坡度是左子树结点之和和右子树结点之和的差的绝对值，所以此题实际上是计算二叉树结点之和的拓展。

具体思路如下：

整个树的坡度就是其所有结点坡度之和，因此给一个变量用以记录结点坡度之和。
结点坡度与左右子树的和有关，因此二叉树递归遍历的目的在于，得到子树的和。

具体代码如下：
class Solution {
public:int count = 0;//记录坡度之和int dfs(TreeNode* root){if(root == nullptr)return 0;//空结点，无值，返回0int sumLeft = dfs(root->left);//左子树的和int sumRight = dfs(root->right);//右子树的和count += abs(sumLeft - sumRight);return root->val + sumLeft + sumRight;//返回树(子树)的所有结点之和}int findTilt(TreeNode* root) {dfs(root);return count;}
};