欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

669. Trim a Binary Search Tree

程序员文章站 2022-06-03 14:06:46
...

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
669. Trim a Binary Search Tree
Example 2:
669. Trim a Binary Search Tree


题解:

package com.leetcode;

public class Solution {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        TreeNode root = new TreeNode(3);
        root.lchild = new TreeNode(0);
        root.rchild = new TreeNode(4);
        root.lchild.rchild = new TreeNode(2);
        root.lchild.rchild.lchild = new TreeNode(1);

        int L = 1;
        int R = 3;

        root = trimBST(root, L, R);
        inorderTraversal(root);
        System.out.println();
    }

    public static TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null)
            return null;

        if (root.value < L) 
            return trimBST(root.rchild, L, R);
        else if (root.value > R)
            return trimBST(root.lchild, L, R);
        else {
            root.lchild = trimBST(root.lchild, L, R);
            root.rchild = trimBST(root.rchild, L, R);
            return root;
        }
    }

    public static void inorderTraversal(TreeNode root) {
        if (root == null)
            return;

        inorderTraversal(root.lchild);
        System.out.print(root.value + " ");
        inorderTraversal(root.rchild);
    }

}

class TreeNode {
    public TreeNode(int value) {
        this.value = value;
        lchild = null;
        rchild = null;
    }

    public int value;
    public TreeNode lchild;
    public TreeNode rchild;
}