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
标签:right,随想录,257,二叉树,path,null,root,节点,left From: https://www.cnblogs.com/cupxu/p/17088879.html