day17

1、leetcode110 平衡二叉树

1. 平衡二叉树：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

2. 递归法

   1. 明确递归函数的参数和返回值

      参数：当前传入节点。
      返回值：以当前传入节点为根节点的树的高度，返回-1 来标记已经不符合平衡树的规则。

   2. 终止条件

      遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

   3. 单层递归逻辑

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

代码实现

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    //返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树，则返回-1
    public int getHeight(TreeNode node){
        if(node == null){
            return 0;
        }

        int leftHeight = getHeight(node.left);//左
        if(leftHeight == -1){
            return -1;
        }

        int rightHeight = getHeight(node.right);//右
        if(rightHeight == -1){
            return -1;
        }

        //中 【return -1表示该树不是平衡二叉树】
        int height = Math.abs(rightHeight - leftHeight) > 1 ? -1 : Math.max(leftHeight, rightHeight) + 1;
        return height;

    }
}

2、leetcode257 二叉树的所有路径

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;
    }

    private 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());
            return;
        }
        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);// 回溯
        }
    }
}

3、leetcode404左叶子之和

1. 左叶子节点【通过父节点判断该节点是否为左叶子节点】

   1. 该节点的左右孩子节点为null（该节点为叶子节点）
   2. 该节点为其父节点的左子节点

2. 思路

   1. 收集左子树的左叶子节点之和；收集右子树的左叶子节点之和；返回给上一层（把左子树左叶子节点之和与右子树的左叶子节点之和相加） === 》 后序遍历
   2. 递归三部曲
      1. 确定递归函数的参数和返回值
         1. 判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
      2. 确定终止条件
         1. 如果遍历到空节点，那么左叶子值一定是0
         2. 如果当前遍历的节点是叶子节点，那其左叶子也必定是0
      3. 确定单层递归的逻辑
         1. 当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。

3. 代码实现

   class Solution {
       public int sumOfLeftLeaves(TreeNode root) {
           if(root == null){
               return 0;
           }
           if(root.left == null && root.right == null){//root为叶子节点
               return 0;
           }
   
           int leftValue = sumOfLeftLeaves(root.left);//左，左子树的左叶子节点之和
           if(root.left != null && root.left.left == null && root.left.right == null){ //左子树为左叶子节点
               leftValue = root.left.val;
           }
   
           int rightVal = sumOfLeftLeaves(root.right);//右，右子树的左叶子节点之和
   
           int sum = leftValue + rightVal;//中，左子树的左叶子节点之和 + 右子树的左叶子节点之和
           return sum;
       }
   }