1
2
3
4
5
6
7
8
9

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

// @lc code=start
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    /// ## 解题思路
    /// - 递归
    /// 1. 先求出链表总长度;
    /// 2. 根据总长度, 将链表分为3个部分: 左半部分, 中间root节点, 右半部分;
    /// 3. 分别使用左半部分链表, 右半部分链表递归生成左子树,右子树;
    /// 4. 综合左右子树及中间root节点, 生成完整的二叉搜索树;
    pub fn sorted_list_to_bst(head: Option<Box<ListNode>>) -> Option<Rc<RefCell<TreeNode>>> {
        if head.is_none() {
            return None;
        }

        type ListNodeOpt = Option<Box<ListNode>>;
        type TreeNodeOpt = Option<Rc<RefCell<TreeNode>>>;

        /// 将list链表的前len个节点转换为二叉搜索树
        fn transfer_to_tree(head: &mut ListNodeOpt, len: usize) -> TreeNodeOpt {
            if len == 0 {
                return None;
            }

            // 先转换左侧len/2个节点为左子树
            let left = transfer_to_tree(head, len / 2);
            //
            if let Some(node) = head {
                // 得到当前节点的下一个节点, 并将head移动到该节点
                *head = node.next.take();

                // 将剩余链表转化为右子树
                let right = transfer_to_tree(head, len - len / 2 - 1);

                // 组装完整二叉搜索树
                Some(Rc::new(RefCell::new(TreeNode {
                    val: node.val,
                    left,
                    right,
                })))
            } else {
                None
            }
        }

        // 统计链表节点总数
        let mut len = 0;
        let mut node = &head;
        while let Some(n) = node {
            len += 1;
            node = &n.next;
        }

        let mut head = head;
        transfer_to_tree(&mut head, len)
    }
}
// @lc code=end

 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
27
28
29

class Solution {
public:
    /*
    ## 解题思路
    * 1. 使用快慢指针查找链表的中间节点；
    * 2. 根据中间节点生成二叉搜索树的根节点；
    * 3. 链表前半部分递归建立左子树；
    * 4. 链表后半部分递归建立右子树；
    */
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!(head->next)) return new TreeNode(head->val);

        auto p0=head, p1=head, p2 = head;
        while (p2&&p2->next) {
            p0=p1;            //中间节点上一个节点
            p1=p1->next;
            p2=p2->next->next;
        }
        p0->next = nullptr;    //从中间节点上一个节点出断开

        //auto midNode = split2SubList(head);
        auto root = new TreeNode(p1->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(p1->next);

        return root;
    }
};