1. 110平衡二叉树
本题平衡的定义是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
- 某节点深度:是到根节点的距离,根节点起始就是1(leetcode定义)
- 某节点高度:是从该到其子叶节点的距离.
(是到它自己的子叶节点,所以下面哪个图,val=0节点的高度是1)
image.png
对应的:
-
求高度就用后序遍历,求深度就用前序遍历.
至于为什么求二叉树最大深度的时候用的是后序遍历,因为:
代码的逻辑其实是求的根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历。
先定义左右两边高度,并判断是-1直接返回-1.
那-1是怎么赋值的呢?就是我们的判断条件.高度差.所以要判断高度差.
(要先判断单边高度,因为-1-(-1) = 0也小于1,但是根本不是我们要的)
剩下的就能返回上一层了,也就是中
2. 257.二叉树所有路径
第一遍刷太难了.完全不知道在分叉路口应该怎么做,脑袋里用现成的方法就是前序.
回溯和递归是相辅相成的,回溯就是比如你已经找到了1->2->5,把5弹出去叫回溯,把2弹出去也叫回溯.
目前用不到,js的递归用的是一直加
- 要准备两个variable,一个res=[]用来存结果,一个curPath = ' '用来存路径
- 重点看下这道题的左右怎么处理的
404.左子叶之和
难点:我们没法判断叶子节点是不是父节点的左孩子,
方法:靠父节点.
image.png
比如这个图里我们想拿6,要在9的地方就判断:
9的左孩子不为空
&&
该左孩子没有左右孩子,也就是是叶子节点
该题用后序比较方便,左右的和直接+就行了
看代码好像出现了三个value,我第一反应是leftValue不会和midValue重叠吗,但是实际上leftValue那部分是递归的必要,不然他怎么往下走呢.而且逻辑是在当前节点计算子节点的值如果是叶子节点的话
