代码随想录算法训练营第十七天|110.平衡二叉树404.左叶子之和-创新互联

110.平衡二叉树

用后序遍历的思想，根节点最后遍历就是为了最后收集子节点信息。
递归 先遍历左子，再右子：这个时候有4种情况：

• 左子 return -1. 因为他发现上一个已经不符合平衡了
• 右子 return -1. 同上
• 当前的递归逻辑计算：>1 直接返回 -1，否则我就继续+1 并且那这个信息传递上去

257. 二叉树的所有路径

1. 首先确定用哪种遍历： 前序 ： 倒推，因为要实现的输出是从root 开始，下一个是他的左子，所以只有前序可以实现这样的输出

但是这道题还是不会丫。。为了打卡先发布，理解了赶紧回来更新TT
(疑惑： 遍历肯定会左右, 那我如何让她只推左子的node进去，或者只推右子进去
解答：用回溯，会把node拿出来 )

404.左叶子之和

难点就是：如何判定 遍历到的叶子节点是 左孩子？
答： 遍历到倒数第二个node的时候(该点的父节点)，看他的左孩子是否为空，如果不空，那这个node的左右节点是不是为null?

if ((node.left != null) && (node.left.left != null) && (node.left.right!= null))
sum += node.left.val;

这个3种遍历都可以：因为只是求一个值，从上往下，或者从下往上上传递数值都可以

我用的是迭代的方法 再结合用后序遍历的模板，相对会比较好写一些。
具体操作如下：按照后序的模板，只不过在Pop出来的node时，对该node进行判断（判断逻辑如上）
最后返回 sum 即可

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧