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

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

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

constructMaximumBinaryTree(int[] nums)
int maxIndex = getMaxIndex(nums, 0, 5) 所以 maxIndex = 3。
树节点根 = 6。
root.left = helper(nums, 0, 2) 所以 maxIndex = 0.
树节点根 = 3。
root.left = helper(nums, 0, -1)，触发基本情况和 returns null.

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

Answer 1

通常，递归方法将一个问题分解为多个子问题，并通过组合它们的解决方案来构建原始问题的解决方案。这也是在这种情况下发生的情况。

最大树的定义本身就是递归的，这样更容易理解解法。请注意，在定义的步骤 2 和 3 中，我们需要从原始数组的子数组构造最大子树。因此我们用更少的输入元素解决了同样的问题。

函数helper是这个解决方案的关键——它从原始输入数组的连续子数组构造最大树。为了更好地理解解决方案，首先忽略具体实现并假设它只是这样做 - nums 参数始终是原始输入数组，low 和 high 以及第一个和第二个的索引子数组中的最后一个元素（包括两者）。 helper returns 为提供的子数组构造的最大树的根。因此对整个数组调用 help 将解决原来的问题。

类似地，getMaxIndex 采用原始数组的子数组（以相同方式指定）和 returns 该子数组中具有最大值的元素的索引。根据最大树的定义，这将是新树中根元素的索引以及我们应该为左右子树拆分数组的索引（定义的第 1 点）。

现在，如果您知道这是这两个函数的作用，那么应该相对容易理解其中的逻辑。

Answer 2

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

步骤为：

constructMaximumBinaryTree(int[] nums)
int maxIndex = getMaxIndex(nums, 0, 5) 所以 maxIndex = 3.
树节点根 = 6.
root.left = helper(nums, 0, 2) 所以 maxIndex = 0.
树节点根 = 3.
root.left = helper(nums, 0, -1)，触发基本情况，returns null.
我们继续处理 root = 3 的右子树，因此 root.right = helper(nums, 1, 2)，maxIndex = 1。
树节点根 = 2.
root.left = helper(nums, 1, 0)，触发基本情况和 returns null.
我们继续处理 root = 2 的右子树，因此 root.right = helper(nums, 2, 2)，maxIndex = 2。
树节点根 = 1.
现在左右return都为null，而我们return到root=6的右子树

Answer 3

我经常发现一些放置得当的打印语句对于理解算法的流程非常有帮助，尤其是当它涉及递归时。我已经更新了您的代码以通过缩进字符串打印正在处理的 child 、 L 或 R 以及级别。

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

public TreeNode helper(int[] nums, int low, int high, String side, String ind){   
  if (high < low){ return null; }

  System.out.println(ind + side + Arrays.toString(Arrays.copyOfRange(nums, low, high+1)));

  //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, "L", ind + "  ");

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

  return root; 
}

根据您的输入结果：

[3, 2, 1, 6, 0, 5]
  L[3, 2, 1]
    R[2, 1]
      R[1]
  R[0, 5]
    L[0]

我认为这使得树的构造更加清晰。

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

How can I walk through this recursive binary tree problem?

java

algorithm

tree

recursion

binary-tree