【二叉树】构造二叉搜索树问题

本文主要介绍如何递归地构造二叉搜索树

一、例题一

题目描述 ： 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例：

思路：

以每个点为树根节点，然后划分出两个区间，分别作为递归地构造左右子树的区间，对每个区间重复执行递归操作。

递归的题目思路总是很好想，但是代码又总是写不出来。

代码：

    public List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> res = new LinkedList<>();
        if(start > end){ // 递归出口，返回空节点
            res.add(null);
            return res;
        }

        for(int i=start; i<=end; i++){ // 枚举所有根节点可能位置

            List<TreeNode> left = generateTrees(start, i-1);
            List<TreeNode> right = generateTrees(i+1, end);

            for(TreeNode leftNode : left){ // 枚举左子树可能情况
                for(TreeNode rightNode : right){ // 枚举右子树可能情况
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = leftNode;
                    treeNode.right = rightNode;
                    res.add(treeNode);
                }
            }
        }

        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二、例题二

题目描述：

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

示例：

思路：

取链表中点构造根节点，中点左侧区间用于递归构造左子树，中点右侧区间用于递归构造右子树。对左右区间重复执行递归过程。

代码：

   public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        return sortedListToBST(list, 0, list.size()-1);
    }


    public TreeNode sortedListToBST(List<Integer> list, int start, int end){
        // 退出条件
        if(start > end){
            return null;
        }
        // 构造根节点
        int index = (start + end) / 2;
        TreeNode node = new TreeNode(list.get(index));
        node.left = sortedListToBST(list, start index-1);
        node.right = sortedListToBST(list, index+1, end);

        return node;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

碎碎念： 太想哭了，早上起来做了个核酸，然后去吃了个饭，反应过来的时候上午已经没了。痛彻心扉，我的宝贵时间，我的财富，我的金钱，啊啊啊啊啊，悟已往之不谏，知来者之可追，加油加油！！！