本次刷题日记的第 50 篇，力扣题为：从根到叶的二进制数之和，简单
一、题目描述：
又是一道二叉树的题，关于二叉树的题相对都是比较简单的，只要想的明白，做起来就会很容易
二、这道题考察了什么思想？你的思路是什么？
题目比较明确，就是让我们从题目给出的二叉树中，找到根节点到每一个叶子节点的路径，再将所有路径求和
稍微不一样的就是每一个路径，我们是需要将路径上的节点组装成 101010 的二进制形式，来进行计算而已，没啥特别的
分析
此处很明显是需要用到二叉树的遍历的，那么我们知道二叉树的递归遍历有 3 种方式
- 前序遍历，根节点 -> 左节点 -> 右节点
- 中序遍历，左节点 -> 根节点 -> 右节点
- 后序遍历，左节点 -> 右节点 -> 根节点
当然，我们使用哪一种遍历的方式，都是可以使用不同的逻辑将题目要求的路线给组装出来，那么咱们任意选择一种，就拿 后序遍历举例子吧
可以看到图中给出二叉树的第一条路，是 1,0,0
那么，我们如何将这 3 个节点，组装成 100 呢？
其实也是比较明确的
- 我们遍历到第 1 个节点的时候， val 赋值为 1
- 遍历到第 2 个节点的时候，val << 1 | 当前节点的值 == 10 | 0 == 10 --> val = 10
- 同样，当遍历到第 3 个节点的时候，val << 1 | 当前节点的值 == 100 | 0 == 100 --> val = 100 = 4
那么遍历第 2 个条路的时候也是同样的道理，也是可以组装成 101 = 5
那么我们在计算结果的时候，咱们不难想到，整棵树的链路是左子树的链路和 + 右子树的链路和
那就有 sum(root) = sum(root.left) + sum(root.right)
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
编码的时候，我们需要注意，当开始遍历的时候，咱们遍历第一个节点的时候，默认值是 0，保证拿到第一个节点的值能直接赋值到 val 上
编码如下：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func helpdfs(node *TreeNode, val int) int { if node == nil{ return 0 } val = val << 1 | node.Val if node.Left == nil && node.Right == nil{ return val } return helpdfs(node.Left, val) + helpdfs(node.Right, val) } func sumRootToLeaf(root *TreeNode) int { return helpdfs(root, 0) }
四、总结：
这么看来，时间复杂度是 O(n) ，因为咱们需要遍历 n 个节点，空间复杂度也是 O(n)，这里不用奇怪，虽然我们没有额外手动开辟 O(n) 的占用空间，但是我们使用递归的话，是需要消耗栈空间的，因此时间复杂也是 O(n)
原题地址：1022. 从根到叶的二进制数之和
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
