这是小川的第381次更新，第410篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第243题（顺位题号是1022）。给定二叉树，每个节点值为0或1.每个根到叶路径表示以最高有效位开始的二进制数。例如，如果路径为0 -> 1 -> 1 -> 0 -> 1，那么这可能表示二进制的01101，即13。
对于树中的所有叶子节点，请考虑从根到该叶子节点的路径所代表的数字。返回这些数字的总和。
例如：
1
/
0 1
/ /
0 1 0 1输入：[1,0,1,0,1,0,1]
输出：22
说明：（100）+（101）+（110）+（111）= 4 + 5 + 6 + 7 = 22
注意：
树中的节点数介于1和1000之间。
node.val是0或1。答案不会超过2^31 - 1。
02 第一种解法
递归的方式解题。
结合题目给的示例来看，可以将该二叉树分为两部分，left和right，left那一支有两条路径100和101，直接做加法就是4+5=9；right那一支也有两条路径110和111，直接做加法就是6+7=13，我们可以将求和拆分成左子树、右子树之和来做。
如果当前节点为空，返回0。如果当前节点如果为叶子节点（没有左子节点和右子节点的节点），就返回此路径所表示的整数。计算路径上的二进制数，可以通用此代码：int val = val*2 + currentNodeValue;，和前天的那道题目在处理累加二进制字符串上类似。
public int sumRootToLeaf(TreeNode root) {
return getSum(root, 0);
}
public int getSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
// 换成 sum = (sum<<1) + root.val; 效果一样
sum = sum*2 + root.val;
// 当前节点为叶子节点时
if (root.left == null && root.right == null) {
return sum;
}
return getSum(root.left, sum) + getSum(root.right, sum);
}03 第二种解法
迭代的方式解题。借助两个栈来实现，思路和上面类似。
public int sumRootToLeaf2(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
// 存节点
Stack<TreeNode> stack = new Stack<TreeNode>();
// 存路径所代表整数
Stack<Integer> prevSum = new Stack<Integer>();
stack.push(root);
prevSum.push(root.val);
while (!stack.isEmpty()) {
TreeNode temp = stack.pop();
Integer tempSum = prevSum.pop();
// 左子树
if (temp.left != null) {
stack.push(temp.left);
prevSum.push(tempSum*2 + temp.left.val);
}
// 右子树
if (temp.right != null) {
stack.push(temp.right);
prevSum.push(tempSum*2 + temp.right.val);
}
// 叶子节点，累加完整路径所表示的整数
if (temp.left == null && temp.right == null) {
sum += tempSum;
}
}
return sum;
}04 小结
算法专题目前已连续日更超过七个月，算法题文章249+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
