平衡二叉树-day13

题目：平衡二叉树
题目链接：https://leetcode.cn/problems/balanced-binary-tree/solutions/377216/ping-heng-er-cha-shu-by-leetcode-solution/
思路：平衡二叉树的定义是：二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。

1. 终止条件root==null 或左右子树高度差大于1
2. 参数：root.left || root.right
3. 单词代码执行逻辑，通过左右根的方式获取树的高度，当root==null,返回；在返回的过程中比较子树的高达差，高度差大于1,返回-1；不大于1，返回最大树的高度
   代码：

点击查看代码

 public boolean isBalanced(TreeNode root) {
        return getHeight(root) !=-1;
    }
    private int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeigh=getHeight(root.left);
        if(leftHeigh==-1){
            return -1;
        }
        int rightHeight=getHeight(root.right);
        if(rightHeight==-1){
            return -1;
        }
        if(Math.abs(leftHeigh-rightHeight)>1){
            return -1;
        }
        return Math.max(leftHeigh,rightHeight)+1;
    }

题目：二叉树的所有路径
题目链接：https://leetcode.cn/problems/binary-tree-paths/solutions/400326/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
思路：1. 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子结点
2. 如果当前结点是叶子节点，则在当前路径末尾添加该节点后我们就得到了1条从根节点到叶子节点的路径，将该路径加入答案即可
代码：

点击查看代码

 public List<String> binaryTreePaths(TreeNode root) {
      List<String> paths=new ArrayList<String>();
      constructPaths(root, "", paths);
      return paths;
    }
    public void constructPaths(TreeNode root,String path,List<String> paths){
        if(root!=null){
            StringBuffer pathSB=new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
             if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            }else{
                 pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }

        }
    }

}

题目：404. 左叶子之和
题目链接：https://leetcode.cn/problems/sum-of-left-leaves/description/
思路：1. 采用后序遍历（左子树→右子树→当前节点），先递归计算左、右子树的左叶子和，再处理当前节点的逻辑，最后合并三者结果；
2. 左叶子识别：当前节点不直接判断自己是否是左叶子（节点无法判断自己是左 / 右孩子），而是判断「自己的左孩子是否是左叶子」—— 这是识别左叶子的关键；
3. 结果合并：最终总和 = 「当前节点的左叶子值（若存在）」 + 「左子树的左叶子和」 + 「右子树的左叶子和」
代码：

点击查看代码

public int sumOfLeftLeaves(TreeNode root) {
        // 1. 递归终止条件：空节点，无任何叶子，贡献和为0
    if (root == null) return 0;
    
    // 2. 递归遍历左子树：求左子树中所有左叶子的和
    int leftValue = sumOfLeftLeaves(root.left);    // 左
    
    // 3. 递归遍历右子树：求右子树中所有左叶子的和
    int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                   
    // 4. 处理当前节点：判断「当前节点的左孩子」是否是左叶子节点
    int midValue = 0; // 初始化为0，若不存在则无贡献
    // 左叶子判定条件：左孩子存在 + 左孩子无左子节点 + 左孩子无右子节点
    if (root.left != null && root.left.left == null && root.left.right == null) { 
        midValue = root.left.val; // 是左叶子，记录其值
    }
    
    // 5. 合并结果：后序遍历的「中」步骤，累加三者贡献
    int sum = midValue + leftValue + rightValue;  // 中
    
    // 6. 返回当前节点为根的子树的左叶子和
    return sum;
    }

题目：222. 完全二叉树的节点个数
题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/description/
思路：题目以及规定了是满二叉树，通过递归的方式
1. 确定终止条件
2. 确定参数
3. 确定单次执行的逻辑
本题：左子树+右子树+1
代码：

点击查看代码

    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }