Как я могу пройти через эту рекурсивную проблему двоичного дерева?

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. TreeNode root = 6.

4. root.left = helper (nums, 0, 2), поэтому maxIndex = 0.

5. TreeNode root = 3.

6. root.left = helper (nums, 0, -1), который запускает базовый случай и возвращает ноль.

Я заблудился после шага 6. После шага 6 возвращается ноль, перейти к 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. TreeNode root = 6.
4. root.left = helper (nums, 0, 2), поэтому maxIndex = 0.
5. TreeNode root = 3.
6. root.left = helper (nums, 0, -1), который запускает базовый случай и возвращает ноль.
7. Перейдем к правильному поддереву для root = 3, поэтому root.right = helper (nums, 1, 2), с maxIndex = 1.
8. TreeNode root = 2.
9. root.left = helper (nums, 1, 0), который запускает базовый случай и возвращает ноль.
10. Перейдем к правильному поддереву для root = 2, поэтому root.right = helper (nums, 2, 2), с maxIndex = 2.
11. TreeNode root = 1.
12. Теперь и левый, и правый возвращают ноль, и мы возвращаемся к правому поддереву root = 6.

Answer 2

Я часто нахожу, что некоторые правильно расположенные операторы печати могут быть чрезвычайно полезны для понимания последовательности алгоритма, особенно когда он включает в себя рекурсию.Я обновил ваш код, чтобы вывести, какой дочерний элемент, 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]

Что, я думаю, делает построение дерева намного более ясным.

Answer 3

Как правило, рекурсивный подход разбивает проблему на несколько подзадач и строит решение исходной проблемы путем объединения их решений.Это точно , что происходит и в этом случае.

Тот факт, что определение максимального дерева само по себе является рекурсивным, облегчает понимание решения.Обратите внимание, что в шагах 2 и 3 определения нам нужно построить максимальное поддерево из подмассива исходного массива.Таким образом, мы решаем ту же проблему с меньшим количеством элементов ввода.

Функция helper является ключом к этому решению - она ​​строит максимальное дерево из непрерывного подмассива исходного массива ввода.Чтобы лучше понять решение, сначала проигнорируйте конкретную реализацию и предположите, что это именно то, что параметр nums всегда является исходным входным массивом, а low и high и индексами первого и последнего элемента в подмассивесоответственно (оба включительно).helper возвращает корень максимального дерева, созданного для предоставленного подмассива.Таким образом, вызов help для всего массива решит исходную проблему.

Аналогичным образом getMaxIndex берет подмассив исходного массива (указанный таким же образом) и возвращает индекс элемента в этом подмассиве, который имеетмаксимальное значениеСогласно определению максимального дерева это будет индекс корневого элемента в новом дереве и индекс, по которому мы должны разделить массив для левого и правого поддеревьев (точка 1 определения).

Теперь, если вы знаете, что это то, что делают две функции, должно быть относительно легко понять логику в них.