java - 如何解决这个递归二叉树问题?-LMLPHP
这是解决问题的有效方法:

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

有人能帮我解决这个问题和所有递归调用吗现在我不明白解决方案是如何构建树节点的。我现在正在这样解决这个问题。
构造最大二叉树(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),它触发基本大小写并返回null。
我在第六步后迷路了。在步骤6返回空值之后,是否转到root.right=helper(nums,maxindex+1,high)?如果是,maxindex和high是什么?接下来的步骤是什么?

最佳答案

简单的回答是“是”,您将移到root.right=helper(nums,maxIndex+1,high),其中maxIndex=0和high=2,所以root.right=helper(nums,1,2)。
步骤如下:
构造最大二叉树(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),它触发基本大小写并返回null。
我们继续对root=3使用右子树,所以root.right=helper(nums,1,2),maxindex=1。
树状根=2。
root.left=helper(nums,1,0),它触发基本大小写并返回null。
我们继续对root=2使用右子树,所以root.right=helper(nums,2,2),maxIndex=2。
树状根=1。
现在左和右都返回null,我们返回到根=6的右子树。

关于java - 如何解决这个递归二叉树问题?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/52603578/

10-17 01:52