给出一棵二叉树,其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
- 例如,如果路径为 0 -> 1 -> 1 -> 0 -> 1,那么它表示二进制数 01101,也就是 13 。
对树上的每一片叶子,我们都要找出从根到该叶子的路径所表示的数字。
返回这些数字之和。题目数据保证答案是一个 32 位 整数。
个人想法:
这是一道树的后序遍历,由题意我们可以知道,先遍历左子树,在遍历右子树,最后遍历根节点,并且遇到叶子结点就返回值。
DFS+二进制
代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int ans=0;
public:
string l;
int dfs(TreeNode* root,int val){
if(root==nullptr){//回溯的判断条件
return 0;
}
val=(val<<1)+root->val;//等同于val=val<<1|root->val;
if(root->left==nullptr && root->right==nullptr) {//叶子结点就返回。
return val;
}
return dfs(root->left,val)+dfs(root->right,val);//左子树+右子树的值
}
int sumRootToLeaf(TreeNode* root) {
return dfs(root,0);
}
};