leecode算法(java版)（二）

红太狼 2022-12-11 02:28 28阅读 0赞

### 34.【108】将有序数组转换为二叉搜索树 ###

//将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 
    //
    // 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 
    //
    // 示例: 
    //
    // 给定有序数组: [-10,-3,0,5,9],
    //
    //一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
    //
    //      0
    //     / \
    //   -3   9
    //   /   /
    // -10  5
    // 
    // Related Topics 树 深度优先搜索

class Solution {
      public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums,0,nums.length-1);
    
      }
      public TreeNode sortedArrayToBST(int [] nums,int left,int right){
        if(left>right)return null;                                        //边界条件，注意是left>right
        int mid=(left+right)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=sortedArrayToBST(nums,left,mid-1);        //递归向左探索，范围变成left~mid-1;
        root.right=sortedArrayToBST(nums,mid+1,right);
        return root;
      }
    }

### 35.【110】 平衡二叉树 ###

//给定一个二叉树，判断它是否是高度平衡的二叉树。 
    //
    // 本题中，一棵高度平衡二叉树定义为： 
    //
    // 
    // 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 
    // 
    //
    // 示例 1: 
    //
    // 给定二叉树 [3,9,20,null,null,15,7] 
    //
    //     3
    //   / \
    //  9  20
    //    /  \
    //   15   7 
    //
    // 返回 true 。 
    // 
    //示例 2: 
    //
    // 给定二叉树 [1,2,2,3,3,null,null,4,4] 
    //
    //        1
    //      / \
    //     2   2
    //    / \
    //   3   3
    //  / \
    // 4   4
    // 
    //
    // 返回 false 。 
    //
    // 
    // Related Topics 树 深度优先搜索

class Solution {
      //这个ReturnNode是参考我描述的递归套路的第二步：思考返回值是什么
      //一棵树是BST等价于它的左、右俩子树都是BST且俩子树高度差不超过1
      //因此我认为返回值应该包含当前树是否是BST和当前树的高度这两个信息
      private class ReturnNode{
        boolean isB;
        int depth;
        public ReturnNode(int depth, boolean isB){
          this.isB = isB;
          this.depth = depth;
        }
      }
      //主函数
      public boolean isBalanced(TreeNode root) {
        return isBST(root).isB;
      }
      //参考递归套路的第三部：描述单次执行过程是什么样的
      //这里的单次执行过程具体如下：
      //是否终止?->没终止的话，判断是否满足不平衡的三个条件->返回值
      public ReturnNode isBST(TreeNode root){
        if(root == null){
          return new ReturnNode(0, true);
        }
        //不平衡的情况有3种：左树不平衡、右树不平衡、左树和右树差的绝对值大于1
        ReturnNode left = isBST(root.left);
        ReturnNode right = isBST(root.right);
        if(left.isB == false || right.isB == false){
          return new ReturnNode(0, false);
        }
        if(Math.abs(left.depth - right.depth) > 1){
          return new ReturnNode(0, false);
        }
        //不满足上面3种情况，说明平衡了，树的深度为左右俩子树最大深度+1
        return new ReturnNode(Math.max(left.depth, right.depth) + 1, true);
      }
    }

### 36.【111】 二叉树的最小深度 ###

//给定一个二叉树，找出其最小深度。 
    //
    // 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 
    //
    // 说明: 叶子节点是指没有子节点的节点。 
    //
    // 示例: 
    //
    // 给定二叉树 [3,9,20,null,null,15,7], 
    //
    //     3
    //   / \
    //  9  20
    //    /  \
    //   15   7 
    //
    // 返回它的最小深度 2. 
    // Related Topics 树 深度优先搜索 广度优先搜索

class Solution {
      public int minDepth(TreeNode root) {
        //当前root为空则返回0
        if(root==null){
          return 0;
        }
        //左子树为空则返回右子树的最小深度
        else if(root.left==null){
          return minDepth(root.right)+1;
        }
        //右子树为空则返回左子树最小深度
        else if(root.right==null){
          return minDepth(root.left)+1;
        }
        //左右子树均不为空则返回左右子树最小深度
        else{
          return Math.min(minDepth(root.left)+1,minDepth(root.right)+1);
        }
      }
    }