二叉树part04 算法

本文主要是介绍二叉树part04 算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树part04

今日任务:

● 110.平衡二叉树
● 257. 二叉树的所有路径
● 404.左叶子之和

1.110.平衡二叉树

110. 平衡二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {/**那么如何标记左右子树是否差值大于1呢？如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。*///一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。//思路：那不就是去求左右两颗子树分别的高度吗//如果高度不超过1，那么继续往下遍历去求//又到高度深度的概念了return getHeight(root)!=-1;}//递归遍历求高度public int getHeight(TreeNode root){if(root==null){return 0;}//还有没有其他的终止条件if(root.left==null&&root.right==null){return 1;}//定义左右子树的分别高度//分别看子树高度int leftHeight=getHeight(root.left);//要加上if(leftHeight==-1){return -1;}int rightHeight=getHeight(root.right);//要加上if(rightHeight==-1){return -1;//因为在函数体前面位置筛选不掉他们}//差值//绝对值int result=Math.abs(leftHeight-rightHeight);if(result>1){result=-1;}else{result=Math.max(leftHeight,rightHeight)+1;//不理解}return result;}
}

2.257. 二叉树的所有路径(递归回溯)

https://leetcode.cn/problems/binary-tree-paths/

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<Integer> arr=new ArrayList<>();List<String> result=new ArrayList<>();// if(root==null)//不存在//返回所有从根节点到叶子节点的路径，那就是根节点到一直深度搜索//搜索到左右孩子都为空了search(root,arr,result);return result;}//将单条路径的节点值保存进数组里面，最后再合成字符串放进字符串集合里面public void search(TreeNode root,List<Integer> arr,List<String> result){//首先将根节点放进数组集合中arr.add(root.val);//终止条件是当root左右孩子都为空时(叶子节点）)if(root.left==null&&root.right==null){//将该路径添加进集合//数组元素加进集合//定义一个字符串String s="";for(int i=0;i<arr.size();i++){s+=arr.get(i);//如果此时i是<length-1,那么就再添加->if(i<arr.size()-1){s+="->";}}//将字符串添加进集合中result.add(s);return;}if(root.left!=null){search(root.left,arr,result);//不要忘记回溯了arr.remove(arr.size()-1);}if(root.right!=null){search(root.right,arr,result);//不要忘记回溯了arr.remove(arr.size()-1);}}
}

3.404.左叶子之和

https://leetcode.cn/problems/sum-of-left-leaves/

要理解左叶子节点和叶子节点的区别

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumOfLeftLeaves(TreeNode root) {return leftValSum(root);}public int leftValSum(TreeNode root){if(root==null){return 0;}//如何判断是左叶子//int leftVal=0;//我们不能这么做，因为这样子只能确定是叶子节点，不能确定是左叶子节点//左节点得是该节点是父节点的左孩子//叶子节点是左右孩子都是空的//遍历到叶子节点，返回现在的左节点值相加赋值给result// if(root.left==null&&root.right==null){//     result+=leftVal;// }//处理中间int midValue=0;//判断左叶子节点(在叶子节点的上一个节点)(同时符合是左节点和叶子节点)if(root.left!=null&&root.left.left==null&&root.left.right==null){midValue+=root.left.val;}//int leftVal=leftValSum(root.left);int rightValue=leftValSum(root.right);int sum=midValue+leftVal+rightValue;return sum;}
}