java - 我该如何解决这个递归二叉树问题？

Question

这是问题的有效解决方案:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return helper(nums, 0, nums.length-1);
    }

    public TreeNode helper(int[] nums, int low, int high){
        if (high < low){ return null; }
        //find max element's index
        int maxIndex = getMaxIndex(nums, low, high);

        //construct root node
        TreeNode root = new TreeNode(nums[maxIndex]);

        //generate left subtree from the left part of subarray
        root.left = helper(nums, low, maxIndex-1);

        //generate right sub tree from the right part of subarray
        root.right = helper(nums, maxIndex+1, high);


        return root; 
    }

    public int getMaxIndex(int[] nums, int low, int high){
        int maxIndex = low;
        for (int i = low+1; i <= high; i++){
            if (nums[i] > nums[maxIndex]){
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

谁能帮我解决这个问题和所有的递归调用？现在我不明白解决方案如何构建树节点。我目前正在解决这样的问题。

1. constructMaximumBinaryTree(int[] nums)

2. int maxIndex = getMaxIndex(nums, 0, 5) 所以 maxIndex = 3。

3. 树节点根 = 6。

4. root.left = helper(nums, 0, 2) 所以 maxIndex = 0。

5. 树节点根 = 3。

6. root.left = helper(nums, 0, -1)，触发基本情况并返回 null。

我在第 6 步后迷路了。在第 6 步返回 null 后，我是否继续执行 root.right = helper(nums, maxIndex+1, high)？如果是这样，maxIndex 和 high 是多少？下一步是什么？

Answer 1

简短的回答是肯定的，你移动到 root.right = helper(nums, maxIndex+1, high)，其中 maxIndex = 0 和 high = 2，所以 root.right = helper(nums, 1, 2)。

步骤是:

1. constructMaximumBinaryTree(int[] nums)
2. int maxIndex = getMaxIndex(nums, 0, 5) 所以 maxIndex = 3。
3. 树节点根 = 6。
4. root.left = helper(nums, 0, 2) 所以 maxIndex = 0。
5. 树节点根 = 3。
6. root.left = helper(nums, 0, -1)，触发基本情况并返回 null。
7. 我们继续处理 root = 3 的右子树，因此 root.right = helper(nums, 1, 2)，maxIndex = 1。
8. 树节点根 = 2。
9. root.left = helper(nums, 1, 0)，触发基本情况并返回 null。
10. 我们继续处理 root = 2 的右子树，因此 root.right = helper(nums, 2, 2)，maxIndex = 2。
11. 树节点根 = 1。
12. 现在left和right都返回null，我们返回root = 6的右子树。