代码随想录 day17 平衡二叉树 二叉树的所有路径 左叶子之和

发布时间 2024-01-12 23:20:41作者: 又见鸣蜩

平衡二叉树

之前一直写迭代代码 没有怎么写递归
正好这题不是很好写迭代 练习一下递归

这题递归逻辑相对简单
左右子树高度差判断是不是大于一 可以直接返回结果
不大于一就高度max(l,r)+1

二叉树的所有路径

关键要点 这题适合先序遍历
回溯过程和递归过程是一起写的
进来几次就回溯几次
这样才能回归到合适位置

精简版本的代码为什么可以不用回溯
由于精简版本的使用的是值拷贝而不是引用
那么回退到上一层节点时 其实path值未发生改变 相当于每一层有一个临时变量
只有到叶子才会被收集 收集完了就回退到根(或者满足左右子树的其他节点)接着收集

左叶子之和

这题比较适合用后序遍历进行递归
因为左叶子需要父节点判断 实际上就是先走到下面再回来