[LeetCode] 426. Convert BST to Sorted Doubly Linke

MartinDai 发布于2019-08-16 13:28 / 2908人阅读

Problem

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

Let"s take the following BST as an example, it may help you understand the problem better:

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.

Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Solution

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Node left = treeToDoublyList(root.left);
        Node right = treeToDoublyList(root.right);
        root.left = root;
        root.right = root;
        return join( join(left, root), right );
    }
    private Node join(Node left, Node right) {
        if (left == null) return right;
        if (right == null) return left;
        Node lastLeft = left.left;
        Node lastRight = right.left;
        
        lastLeft.right = right;
        right.left = lastLeft;
        lastRight.right = left;
        left.left = lastRight;
        
        return left;
    }
}

服务器托管超融合服务器 Doubly BST Sorted LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71803.html

[LeetCode] 109. Convert Sorted List to Binary Sear

Problem Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in whi...

dongfangyiyu 2019-08-16 13:42 评论0 收藏0
[LintCode/LeetCode] Convert Sorted List to Balance

摘要：当链表为空时，中出现大于，返回。然后计算中点，以为界分别递归构建左右子树。顺序是，左子树根结点右子树。由于根节点是直接取构建，当前的已经被取用。所以在下一次递归构建右子树之前，要让指向。最后将和左右子树相连，返回。 Problem Given a singly linked list where elements are sorted in ascending order, conve...

Michael_Ding 2019-08-14 15:32 评论0 收藏0
[Leetcode] Convert Sorted Array/List to Binary Sea

摘要：我们可以用和两个值来限定子树在链表中的位置，通过递归的方式，深入找到最左边，然后开始顺序遍历链表链表当前节点作为全局变量，这样无论递归在哪我们都能拿到，同时建树。代码先递归的计算左子树创造根节点最后递归的计算右子树 Convert Sorted List to Binary Search Tree Given a singly linked list where elements ar...

wpw 2019-08-14 12:40 评论0 收藏0
[Leetcode-Tree] Convert Sorted Array to Binary Sea

摘要：解题思路平衡二叉树，其实就是数组中间的数作为根，利用递归实现左子树和右子树的构造。 Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST. 1.解题思路平衡二叉树，...

songze 2019-08-16 10:26 评论0 收藏0
leetcode109. Convert Sorted List to Binary Search

摘要：题目要求给一个按照递增顺序排列的链表。将该链表转化为平衡二叉树。思路和代码在这里需要注意的是，因为提供的数据结构为链表，所以我们必须顺序遍历才能知道该链表的长度以及该链表的中间位置。并依次递归左子节点和右子节点。题目要求 Given a singly linked list where elements are sorted in ascending order, convert i...

高胜山 2019-08-15 11:08 评论0 收藏0