110.平衡二叉树
-
平衡二叉树的定义：任何节点的左右子树高度差绝对值不超过1 空树也是AVL!
-
确定遍历顺序：
求高度用后序，求深度用前序。（取决于需不需要从下往上返回结果）
先判断它是不是平衡二叉树 如果是就返回 如果不是就记录一下它的最大高度。
递归函数
- 递归函数参数和返回值
int getHeight(TreeNode node)
- 确定递归终止条件
如果发现左子树和右子树高度差大于1了，我们直接return -1，告诉上一层已经不是AVL树了
if(node == null) return 0;
- 单层递归逻辑
后序遍历：左 右 中
leftHeight = getHeight(node.left); //左
if(leftHeight == -1) return -1;
leftRight = getHeight(node.right); //右
if(rightHeight == -1) return -1;
//能进到这说明属于左右子树AVL的条件，看高度差
if(abs.(leftHeight-rightHeight) > 1) //中
result = -1;
else
result = 1 + max(leftHeight, rightHeight);
return result;
- java代码
class Solution {
public int getHeight(TreeNode node) {
if(node == null) return 0;
int leftHeight = getHeight(node.left);
if(leftHeight == -1) return -1;
int rightHeight = getHeight(node.right);
if(rightHeight == -1) return -1;
int result = 0;
if(Math.abs(leftHeight - rightHeight) > 1) result = -1;
else result = 1 + Math.max(leftHeight, rightHeight);
return result;
}
public boolean isBalanced(TreeNode root) {
boolean flag;
return flag = getHeight(root) >= 0 ? true : false;
}
}
257.二叉树的所有路径
- 确定遍历顺序
我们只能用前序遍历。只有前序（中左右）先遍历父节点，才能让根节点一路指下去，让父节点指向孩子节点。
回溯？
- 其实就是一个回退的过程，与递归结合在一起的。
这条路走到头了，就回退到原来的位置再重新开始走另一条路。
- 确定递归函数
void traversal(TreeNode node, List<Integer> path, List<String> result)
path数组记录其中的一条路径，result数组存放所有的结果。
- 确定终止条件
if(node.left == null && node.right == null) {
result.add(path); //省略转化逻辑
}
遍历到叶子节点了就停，收获当前结果。
- 单层递归逻辑
前序顺序：中左右
我们每遍历到一个节点，就要把这个节点添加进path里。
path.add(node.val); //中
注意这一句要放在递归函数进来的第一句！不然到叶子节点还没记录就添加结果了
接下来写左 和 右。有没有可能node.left(right)为空也进到下一层递归呢？此时path.add(node.val)，结点为空。所以在左右递归之前要先判断是否不为空才遍历。
if(node.left) {
traversal(node.left,path,result);
path.remove(); //恢复现场 回溯的过程
}
if(node.right) {
traversal(node.right,path,result);
path.remove(); //恢复现场 回溯的过程
}
有递归，就有回溯！退出递归的时候，表示已经收集到了结果或者遍历完了，此时弹出一个元素恢复现场。
这题我们设定是到叶子节点就停下来，不要让空节点进入到递归！所以可以在第一句就add，然后往左右递归之前也要判断是否左右孩子为空
list
- 完整java代码
class Solution {
public void traversal(TreeNode node, List<Integer> path, List<String> res) {
path.add(node.val); //这一句实际就是处理“中”的逻辑
if(node.left == null && node.right == null) { //遇到了叶子节点就收集
StringBuilder sb = new StringBuilder();
for(int i = 0; i < path.size()-1; i++) { //在前n-1个数字后面拼上个"->"
sb.append(path.get(i));
sb.append("->");
}
sb.append(path.get(path.size()-1)); //把最后一个数字拼上去
res.add(sb.toString()); //收集这一条路径
return; //一直收集到叶子节点才会返回！
}
//递归遍历左和右 记得判断不为空+回溯恢复现场
if(node.left != null) {
traversal(node.left, path, res);
path.remove(path.size()-1);
}
if(node.right != null) {
traversal(node.right, path, res);
path.remove(path.size()-1);
}
}
public List<String> binaryTreePaths(TreeNode root) {
List<Integer> path = new ArrayList<>();
List<String> res = new ArrayList<>();
traversal(root,path,res);
return res;
}
}
404.左叶子之和
左叶子？
首先一定是个叶子节点（左右孩子都为空），其次一定是它父节点的左孩子！（根节点一定不是）
之前的题目，我们都是遍历到一个元素，才判断这个元素是不是符合的 我们要进行收集，但是这题不一样！
判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
遍历顺序
用后序比较简洁，因为要一层一层向上返回。父节点只要把左子树的左叶子和 与 右子树的左叶子和相加就行。
递归函数
- 递归函数
int traversal(TreeNode node)
- 终止条件
if(node == null) return 0;
if(node.left == null && node.right == null) { //只是遇到叶子节点
return 0;
}
遇到叶子节点也要return 0（因为它的左子树和右子树都没有左叶子之和）
- 单层逻辑
int leftSum = traversal(node.left); //收集左子树里的左叶子和
if(node.left != null && node.left.left == null && node.left.right == null) //如果左孩子不为空 且左孩子是叶子节点
leftSum = node.left.val; //收集
int rightSum = traversal(node.right); //收集右子树里的左叶子和
return leftSum + rightSum; //中
- 完整代码
class Solution {
public int traversal(TreeNode node) {
if(node == null) return 0;
if(node.left == null && node.right == null) return 0; //叶子节点的左右子树 左叶子和为0
int leftSum = traversal(node.left); //收集左子树里的左叶子和
if(node.left != null && node.left.left == null && node.left.right == null) //如果左孩子不为空 且左孩子是叶子节点
leftSum = node.left.val; //收集
int rightSum = traversal(node.right); //收集右子树里的左叶子和
return leftSum + rightSum; //中
}
public int sumOfLeftLeaves(TreeNode root) {
return traversal(root);
}
}
理解这两个递归终止条件！不是为了收集值服务的，是为了终止递归。
day17总结
-
List可以用
list.get(i)获取第i个元素List用
list.remove(i)删除第i个元素List长度是
list.size() -
StringBuilder转换为String用
sb.toString()
