110.平衡二叉树

110. 平衡二叉树

思路：

分别求出每个节点其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

代码实现：

 一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。*/class Solution {public boolean isBalanced(TreeNode root) {//后序遍历+剪枝(从底至顶)return recur(root)!=-1;}public int recur(TreeNode root){if(root==null){return 0;}//注意这里是return 0int leftDepth=recur(root.left);if(leftDepth==-1){return -1;}int rightDepth=recur(root.right);if(rightDepth==-1){return -1;}return Math.abs(leftDepth-rightDepth)<2?Math.max(leftDepth,rightDepth)+1:-1;//如果当前节点的左右子树的深度差小于2则返回左右深度的较大者加1，否则返回-1}
}

257.二叉树的所有路径

1.递归+回溯这个解法不太理解

2.DFS递归：每个节点访问的时候不是把他打印出来，而是先把他存储起来，到叶子结点的时候再添加到集合中，最后返回集合的值；

如果是叶子节点，说明找到一条路径，把它加入到res中，如果不是叶子节点则继续dfs遍历左右子节点；如果是非叶子节点，

257. 二叉树的所有路径

/*** 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<String> res = new ArrayList<>();// 存最终的结果if (root == null) {return res;}List<Integer> paths=new ArrayList<>();traversal(root,paths,res);return res;}public void traversal(TreeNode root,List<Integer>paths,List<String> res){paths.add(root.val);//前序遍历，中//遇到叶子节点if(root.left==null&&root.right==null){//输出StringBuilder sb=new StringBuilder();//for(int i=0;i<paths.size()-1;i++){sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size()-1));//记录最后一个节点res.add(sb.toString());}//递归和回溯同时进行，放在同一个括号中if(root.left!=null){traversal(root.left,paths,res);paths.remove(paths.size()-1);//回溯}if(root.right!=null){traversal(root.right,paths,res);paths.remove(paths.size()-1);//回溯}}
}
//1，深度优先搜索（递归写法）,每个节点访问的时候不是把他打印出来，而是先把他存储起来，到叶子结点的时候再添加到集合中，最后返回集合的值class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();dfs(root, "", res);return res;}private void dfs(TreeNode root, String path, List<String> res) {//如果为空，直接返回if (root == null)return;//如果是叶子节点，说明找到了一条路径，把它加入到res中if (root.left == null && root.right == null) {res.add(path + root.val);return;}//如果不是叶子节点，在分别遍历他的左右子节点dfs(root.left, path + root.val + "->", res);dfs(root.right, path + root.val + "->", res);}}

404.左叶子之和

思路，这道题AC出乎意料，分别求出root的左右子树的左叶子节点之和，然后二者相加就是答案。

关于左叶子节点的判断要通过其父节点来判断，如果父节点root的左孩子不为空，左孩子的左右孩子为空，说明root的左孩子是叶子节点

404. 左叶子之和

代码实现：

class Solution {public int sumOfLeftLeaves(TreeNode root) {//节点A的左孩子为空，且左孩子的左右孩子都为空，说明这个左孩子是左叶子//求root节点的  左子树的所有左叶子节点之和+右子树的所有左叶子节点之和if(root==null){return 0;}int leftSum=sumOfLeftLeaves(root.left);int rightSum=sumOfLeftLeaves(root.right);if(root.left!=null&&root.left.left==null&&root.left.right==null){//说明root的左孩子是叶子节点，即左叶子leftSum+=root.left.val;}return leftSum+rightSum;}
}