内容简介：给予一颗二叉树，每个节点的值只有 0 和 1, 每个根到叶子节点的路径都是一个有效的二进制树, 如:对于树中的所有叶子节点, 请返回根节点到这些叶子节点的路径所代表的二进制值的和.例 :
给予一颗二叉树，每个节点的值只有 0 和 1, 每个根到叶子节点的路径都是一个有效的二进制树, 如: 0 -> 1 -> 1 -> 0 -> 1
, 那么用二进制表示就是 01101
, 对应十进制为 13
.
对于树中的所有叶子节点, 请返回根节点到这些叶子节点的路径所代表的二进制值的和.
例 :
给予树：
1
/ \
0 1
/ \ / \
0 1 0 1
返回: 22.
说明: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
解法
采用深度优先遍历, 从跟节点开始, 到下一层的时候, 将父节点的值向左移动一位, 再加上当前节点的值, 直到根节点为止.
如上图中, 1 -> 0 -> 0
这个路径, 从根节点 1 开始, 到第二层, 对 1 左移一位 i = 1 << 1
, 等于 10
, 再加上当前节点的值 0
等于 10
, 再到下一层, 向左移动一位 i = 10 << 1
, 等于 100
.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int result = 0;
public int sumRootToLeaf(TreeNode root) {
dfs(root, 0);
return result;
}
public void dfs(TreeNode node, int currentVal) {
if (node != null) {
currentVal <<= 1;
currentVal += node.val;
if (node.left == null && node.right == null) {
result += currentVal;
}
dfs(node.left, currentVal);
dfs(node.right, currentVal);
}
}
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Sum of Root To Leaf Binary Numbers. Memory Usage: 35.4 MB, less than 100.00% of Java online submissions for Sum of Root To Leaf Binary Numbers.
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Web Data Mining
Bing Liu / Springer / 2011-6-26 / CAD 61.50
Web mining aims to discover useful information and knowledge from Web hyperlinks, page contents, and usage data. Although Web mining uses many conventional data mining techniques, it is not purely an ......一起来看看 《Web Data Mining》 这本书的介绍吧!
