[LeetCode] 426. Convert BST to Sorted Doubly Linke

MartinDai 發布于2019-08-16 13:28 / 3002人閱讀

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

GPU云服務器云服務器 Doubly BST Sorted LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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