資訊專欄INFORMATION COLUMN
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/71803.html
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...
摘要：當(dāng)鏈表為空時(shí)，中出現(xiàn)大于，返回。然后計(jì)算中點(diǎn)，以為界分別遞歸構(gòu)建左右子樹。順序是，左子樹根結(jié)點(diǎn)右子樹。由于根節(jié)點(diǎn)是直接取構(gòu)建，當(dāng)前的已經(jīng)被取用。所以在下一次遞歸構(gòu)建右子樹之前，要讓指向。最后將和左右子樹相連，返回。 Problem Given a singly linked list where elements are sorted in ascending order, conve...
摘要：我們可以用和兩個(gè)值來(lái)限定子樹在鏈表中的位置，通過(guò)遞歸的方式，深入找到最左邊，然后開始順序遍歷鏈表鏈表當(dāng)前節(jié)點(diǎn)作為全局變量，這樣無(wú)論遞歸在哪我們都能拿到，同時(shí)建樹。代碼先遞歸的計(jì)算左子樹創(chuàng)造根節(jié)點(diǎn)最后遞歸的計(jì)算右子樹 Convert Sorted List to Binary Search Tree Given a singly linked list where elements ar...
摘要：解題思路平衡二叉樹，其實(shí)就是數(shù)組中間的數(shù)作為根，利用遞歸實(shí)現(xiàn)左子樹和右子樹的構(gòu)造。 Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST. 1.解題思路平衡二叉樹，...
摘要：題目要求給一個(gè)按照遞增順序排列的鏈表。將該鏈表轉(zhuǎn)化為平衡二叉樹。思路和代碼在這里需要注意的是，因?yàn)樘峁┑臄?shù)據(jù)結(jié)構(gòu)為鏈表，所以我們必須順序遍歷才能知道該鏈表的長(zhǎng)度以及該鏈表的中間位置。并依次遞歸左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。 題目要求 Given a singly linked list where elements are sorted in ascending order, convert i...
閱讀 2582·2021-09-06 15:02
閱讀 3214·2021-09-02 10:18
閱讀 2837·2019-08-30 15:44
閱讀 696·2019-08-30 15:43
閱讀 1959·2019-08-30 14:08
閱讀 2768·2019-08-30 13:16
閱讀 1409·2019-08-26 13:52
閱讀 939·2019-08-26 12:21
