给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

分析

根节点需要做什么？

  1. public TreeNode constructMaximumBinaryTree(int[] nums) {
  2.     // 找到数组中的最大值
  3.     int maxValue = 
  4.     // 找到最大值的索引
  5.     int maxValueIndex = 
  6.     // 根据最大值的索引拆分数组
  7.     int[] leftArr =
  8.     int[] rightArr = 
  9.     // 构建根节点
  10.     TreeNode root = new TreeNode(maxValue);
  11.     // 构建根节点左子树
  12.     root.left = constructMaximumBinaryTree(leftArr);
  13.     // 构建根节点右子树
  14.     root.right = constructMaximumBinaryTree(rightArr);
  15. }

找到数组中的最大值和最大值的索引

  1. // 找到数组中的最大值
  2. int maxValue = nums[0];
  3. // 找到最大值的索引
  4. int maxValueIndex = 0;
  5. for(int i = 0; i < nums.length; i++) {
  6.     if(nums[i] > maxValue) {
  7.         maxValue = nums[i];
  8.         maxValueIndex = i;
  9.     }
  10. }

根据最大值的索引拆分数组

  1. // 根据最大值的索引拆分数组
  2. int maxValueIndex = 
  3. int[] leftArr = new int[maxValueIndex];
  4. int[] rightArr = new int[nums.length - 1 - maxValueIndex];
  5. for(int i = 0; i < maxValueIndex; i++) {
  6.     leftArr[i] = nums[i];
  7. }
  8. for(int i = maxValueIndex + 1, j = 0; i < nums.length; i++, j++) {
  9.     leftArr[j] = nums[i];
  10. }

完整递归算法

  1. public TreeNode constructMaximumBinaryTree(int[] nums) {
  2.     if(nums == null || nums.length == 0) {
  3.         return null;
  4.     }
  5.     // 找到数组中的最大值
  6.     int maxValue = nums[0];
  7.     // 找到最大值的索引
  8.     int maxValueIndex = 0;
  9.     for(int i = 0; i < nums.length; i++) {
  10.         if(nums[i] > maxValue) {
  11.             maxValue = nums[i];
  12.             maxValueIndex = i;
  13.         }
  14.     }
  15.     // 根据最大值的索引拆分数组
  16.     int[] leftArr = new int[maxValueIndex];
  17.     int[] rightArr = new int[nums.length - 1 - maxValueIndex];
  18.     for(int i = 0; i < maxValueIndex; i++) {
  19.         leftArr[i] = nums[i];
  20.     }
  21.     for(int i = maxValueIndex + 1, j = 0; i < nums.length; i++, j++) {
  22.         rightArr[j] = nums[i];
  23.     }
  24.     // 构建根节点
  25.     TreeNode root = new TreeNode(maxValue);
  26.     // 构建根节点左子树
  27.     root.left = constructMaximumBinaryTree(leftArr);
  28.     // 构建根节点右子树
  29.     root.right = constructMaximumBinaryTree(rightArr);
  30.     return root;
  31. }

进一步分析

每一次递归做了什么？
找索引范围为 [left,right] 的数组中的最大值作为 root 节点，然后将数组划分成[l, mid-1]和[mid+1,r]两段，并分别构造成root的左右两棵子最大二叉树

  1. private static TreeNode constructMaximumBinaryTree(int[] nums, int leftIndex, int rightIndex) {
  2.     if (leftIndex > rightIndex) {
  3.         return null;
  4.     }
  5.     // 找到数组索引[leftIndex,rightIndex]范围内最大的值
  6.     int maxValue = nums[0];
  7.     // 找到最大值的索引值
  8.     int maxValueIndex = leftIndex;
  9.     for(int i = leftIndex; i <= rightIndex; i++) {
  10.         if(nums[i] > maxValue) {
  11.             maxValue = nums[i];
  12.             maxValueIndex = i;
  13.         }
  14.     }
  15.     // 构建根节点
  16.     TreeNode root = new TreeNode(maxValue);
  17.     // 构建根节点左子树
  18.     root.left = constructMaximumBinaryTree(nums, leftIndex, maxValueIndex - 1);
  19.     // 构建根节点右子树
  20.     root.right = constructMaximumBinaryTree(nums, maxValueIndex + 1, rightIndex);
  21.     return root;
  22. }

优化后完整递归算法

  1. public TreeNode constructMaximumBinaryTree(int[] nums) {
  2.     return constructMaximumBinaryTree(nums, 0, nums.length - 1);
  3. }
  5. private TreeNode constructMaximumBinaryTree(int[] nums, int leftIndex, int rightIndex) {
  6.     if (leftIndex > rightIndex) {
  7.         return null;
  8.     }
  9.     // 找到数组索引[leftIndex,rightIndex]范围内最大的值
  10.     int maxValue = nums[0];
  11.     // 找到最大值的索引值
  12.     int maxValueIndex = leftIndex;
  13.     for(int i = leftIndex; i <= rightIndex; i++) {
  14.         if(nums[i] > maxValue) {
  15.             maxValue = nums[i];
  16.             maxValueIndex = i;
  17.         }
  18.     }
  19.     // 构建根节点
  20.     TreeNode root = new TreeNode(maxValue);
  21.     // 构建根节点左子树
  22.     root.left = constructMaximumBinaryTree(nums, leftIndex, maxValueIndex - 1);
  23.     // 构建根节点右子树
  24.     root.right = constructMaximumBinaryTree(nums, maxValueIndex + 1, rightIndex);
  25.     return root;
  26. }

测试算法

  1. int[] arr = {3,2,1,6,0,5};
  2. TreeNode root = constructMaximumBinaryTree(arr);
  3. BinaryTreePrintUtil.print(root);
  1.     6            
  2.  /     \         
  3. 3       5      
  4.  \     /        
  5.   2   0          
  6.    \             
  7.     1