非递归思路
看leetcode上的题解,大部分人用了递归的写法。这里给出一个非递归的方法。
二叉搜索树具有这样的性质:其左子树上的节点的值都小于等于根节点的值,
其右子树上的节点的值都大于等于根节点的值;
题目要求:获得一个排序的双向链表,要求不创建任何新的节点,只调整树中节点指针的指向。
立即想到中序遍历可得到二叉搜索树的升序序列。可以在中序遍历二叉树的非递归算法的基础上,
利用pre变量存储节点的前驱,head存放中序遍历的第一个节点,tail存放中序遍历的最后一个节点,
将二叉搜索树串联成一个双链表。
非递归
class Solution {
public:
Node *head, *tail;//head存放双链表的头结点,tail存放双链表的尾节点
Node* treeToDoublyList(Node* root) {
if(!root) return NULL;//防止越界
inOrder(root);//中序遍历改造二叉搜索树
head->left = tail;//使头结点的前驱指向尾节点
tail->right = head;//使尾节点的后继指向头节点
return head;
}
void inOrder(Node* root){//中序遍历改造二叉搜索树
if(!root)return ;
stack<Node*> stk;//用一个栈存放遍历时得到的节点
//本算法的核心思想就在于:利用栈进行的二叉树中序遍历过程
//节点出栈的顺序和中序遍历的顺序是完全一致的
Node* pre = NULL;//pre代表前驱节点
while(!empty(stk) || root){//当栈不空或root不为空时循环继续
while(root){//沿左孩子走下去
stk.push(root);
root = root->left;
}
root = stk.top();//此时root->left == NULL
if(!pre)//若前驱为空代表root为中序遍历的第一个节点
head = root;
else
pre->right = root;//将前驱的right指向root
root->left = pre;//将root的left指向前驱
pre = root;//前驱移动至root
stk.pop();//栈顶元素 == root,此时root已经被加入链表中,将栈顶元素出栈
root = root->right;//root走至其右孩子处
if(empty(stk) && !root)//若栈空且root也为空
//则树中所有节点都已经被遍历过,pre此时代表最后一个节点
tail = pre;
}
}
};
执行用时:4 ms, 在所有 Cpp 提交中击败了99.68%的用户
内存消耗:7.8 MB, 在所有 Cpp 提交中击败了66.14%的用户
递归写法
//递归的方法相对简单一些
class Solution {
public:
Node *head, *pre;//递归结束后,pre就是最后一个节点
Node* treeToDoublyList(Node* root) {
if(!root) return NULL;
inOrder(root);
head->left = pre;
pre->right = head;
return head;
}
void inOrder(Node* root){//中序遍历递归改造二叉搜索树
if(!root)return;
inOrder(root->left);//中序遍历
if(!pre)//若pre == NULL,说明当前节点是中序遍历的第一个节点
head = root;
else
pre->right = root;
root->left = pre;
pre = root;//更新pre
inOrder(root->right);
}
};