算法基础十五

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3] 输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

 public TreeNode sortedArrayToBST(int[] nums) {
   
        return helper(nums, 0 , nums.length - 1);
    }

    private TreeNode helper(int[] nums, int left, int right) {
   
        if (left > right) {
   
            return null;
        }

        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true

 public boolean isBalanced(TreeNode root) {
   
        if (root == null) {
   
            return true;
        }

        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int height(TreeNode root) {
   
        if (root == null) {
   
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }

二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5

    public int minDepth(TreeNode root) {
   
        if (root == null) {
   
            return 0;
        }

        if (root.left == null && root.right == null) {
   
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
   
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
   
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }

路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径： (1 -->2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

    public boolean hasPathSum(TreeNode root, int targetSum) {
   
        if (root == null) {
   
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()) {
   
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if (now.left == null && now.right == null) {
   
                if (temp == targetSum) {
   
                    return true;
                }
                continue;
            }
            if (now.left != null) {
   
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if (now.right != null) {
   
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]

    public List<List<Integer>> generate(int numRows) {
   
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
   
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
   
                if (j == 0 || j == i) {
   
                    row.add(1);
                } else {
   
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }