温馨提示:本文翻译自stackoverflow.com,查看原文请点击:java - Trim Binary Search Tree Using Recursion

java - 使用递归修剪二进制搜索树

发布于 2020-03-27 10:31:31

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

我知道我在递归代码中的某个地方搞砸了,并将值设为null并再次使用它,我觉得我非常接近解决方案。我无法自行解决。请帮帮我。

查看更多

查看更多

提问者
Mridul Mittal
被浏览
131
mnestorov 2019-07-03 21:30

在这种情况下对您不起作用的原因是,最后您需要递归获取new 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;作为一个命中,您还必须在这里使用递归。

发布
问题

分享
好友

手机
浏览

扫码手机浏览