LeetCode 110.平衡二叉树
分析1.0
求左子树高度和右子树高度，若高度差>1，则返回false，所以我递归了两遍
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int left = postOrder(root.left);
int right = postOrder(root.right);
if(Math.abs(left-right)>1){
return false;
}
return true;
}
public int postOrder(TreeNode p){
if(p == null){
return 0;
}
int left = postOrder(p.left);
int right = postOrder(p.right);
return Math.max(left,right)+1;
}
}失误
若在遍历过程中已经发现高度不平衡了，那这时其实就该返回false，但是返回结果类型是高度int，只能用特殊值来指代这种情况,遍历过程中发现不平衡了就返回-1，发现当前节点是-1了就该返回-1
分析2.0
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return postOrder(root) == -1 ? false : true;
}
public int postOrder(TreeNode p){
if(p == null){
return 0;
}
int left = postOrder(p.left);
if(left == -1) return -1;
int right = postOrder(p.right);
if(right == -1) return -1;
if(Math.abs(left-right)>1) {
return -1;
}
return Math.max(left,right)+1;
}
}LeetCode 257. 二叉树的所有路径
分析1.0
模拟访问路径的过程，从根节点访问到最左叶节点 ，访问过程中不断push经过的节点
逻辑：
path加入当前节点、如果当前节点是叶节点，添加path，返回，删除当前加入的节点；如果是左节点或右节点，进入递归；
关键在于递归时什么时候删除访问过的节点，访问左节点完了删除左节点，访问右节点完了删除右节点，访问自己完了，删除自己
class Solution {
List<String> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<String> binaryTreePaths(TreeNode root) {
preOrder(root);
// 这里也可以看做是一次递归 递归结束后才能删除本节点
// path.remove(path.size() - 1);
System.out.println("path为-----"+path);
return res;
}
public void preOrder(TreeNode p){
// 对当前节点进行操作 节点的数目范围在[1,100] 肯定有节点，不必判空
path.add(p.val);
// 到达叶节点 遍历完一条路径 此条路径加入当前节点后回溯
if(p.left == null && p.right == null){
//System.out.println("当前叶子节点"+p.val);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < path.size() - 1; i++){
sb.append(path.get(i)).append("->");
}
res.add(sb.append(path.get(path.size() - 1)).toString());
return;
}
// 遍历左子树
if(p.left != null){
//加入节点
//System.out.println(p.left.val);
preOrder(p.left);
// 删除节点
//System.out.println("删除的节点"+path.get(path.size()-1));
// 这里也要回溯删除加入的节点和->
path.remove(path.size() - 1);
}
// 遍历右子树
if(p.right != null){
preOrder(p.right);
// 这里也要回溯删除加入的节点和->
path.remove(path.size() - 1);
}
//path.remove(path.size() - 1); //这里不能再删除了 前面递归结束已经删除一次了
}
}LeetCode 404.左叶子之和
分析1.0
递归，但是递归的过程中要判断一个节点是否为左叶子
失误
光想着节点本身了，但是光凭借节点自身的信息无发判断一个节点是左孩子还是右孩子，左右孩子是通过父节点指针来确定的，叶子节点则再加一个限制
分析2.0
遍历节点，if当前节点cur为空，返回，if左孩子的左右节点都为null，则cui.left为左叶子
if(root.left != null && root.left.left == null && root.left.right == null) 访问节点保证节点非null
class Solution {
int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
preOrder(root);
return sum;
}
public void preOrder(TreeNode root){
if(root == null){
return;
}
if(root.left != null && root.left.left == null && root.left.right == null){
sum+=root.left.val;
}
preOrder(root.left);
preOrder(root.right);
}
}总结
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
回溯要和递归永远在一起，递归后一定要回溯，必须在同一个代码块中
当前节点为空，直接返回，不用再考虑left right节点了
操作某个节点，一定要保证这个节点不为空
方法只执行一次，可以看做只递归一次； 递归主体逻辑，结束条件，返回参数+形式参数，先判是结束递归，还是先执行递归逻辑，递归后又该如何做
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch、var
