Обрезать бинарное дерево поиска с помощью рекурсии - PullRequest
Новая
       14

Обрезать бинарное дерево поиска с помощью рекурсии

1 голос
/ 03 июля 2019

TRIM BST Учитывая двоичное дерево поиска и самые низкие и самые высокие границы как L и R, урежьте дерево так, чтобы все его элементы были в [L, R] (R> = L). Возможно, вам потребуется изменить корень дерева, поэтому в результате должен быть возвращен новый корень урезанного двоичного дерева поиска.

Я новичок и только начал изучать рекурсию. Я написал код, как написано ниже. Он работает некоторые из тестовых случаев и дает исключение Null Pointer для остальных. Я знаю решение проблемы (также написано ниже), но я хочу исправить свой код, а не писать так, как написано решение.

вот моя попытка. 

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
    if(root==null)
    {
        return root;
    }
    if(root.val<L)
    {
        root=root.right;
        if(root==null)
        {
            return root;
        }
    }
     if(root.val>R)
    {
        root=root.left;
          if(root==null)
        {
            return root;
        }
    }
     if(root.left!=null)
    {
        if(root.left.val<L)
        {
            root.left=root.left.right;
        }

    }
     if(root.right!=null)
    {
        if(root.right.val>R)
        {
            root.right=root.right.left;
        }

    }
    trimBST(root.left,L,R);
    trimBST(root.right,L,R);
    return root;

}
}

выдает ошибку для 

    [3,1,4,null,2]
3
4

вот решение 

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return root;
        if (root.val > R) return trimBST(root.left, L, R);
        if (root.val < L) return trimBST(root.right, L, R);

        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

я знаю, что где-то испортил код рекурсии и сделал значение пустым и снова его использую, и я чувствую, что я очень близок к решению. Я не могу понять это самостоятельно. Пожалуйста, помогите мне.

1 Ответ

0 голосов
/ 03 июля 2019

Причина, по которой он не работает в этом случае, заключается в том, что в конце вам нужно рекурсивно получить новый root. То есть trimBST(root.left, L, R); будет рекурсивно спускаться по дереву, но в конце концов вернется к нулю. Таким образом, вам нужно будет присвоить его левой или правой стороне дерева. 

root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);

Но после этого у вас также будет другая проблема, связанная с root=root.right; и root=root.left;. В качестве хита вы должны использовать здесь и рекурсию.

...