问题描述:
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
这道题目注意审题,注意双向链表的表头和表尾部是否连接,如果连接就是一个循环双向链表。
循环双向链表+递归
思路上很直接,在二叉搜索树的中序遍历基础上,改变当前节点root
指针指向,因为我们需要将root->left
指向前一个顺序遍历的节点,我们用一个指针pre
表示当前节点的前一个节点。
解法一
递归返回头节点和尾节点,注意递归传递的参数应该是引用类型(不然debug搞死你。。。)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| Node* treeToDoublyList(Node* root) { if(!root) return root; Node*head=nullptr,*pre=nullptr; dfs(root,head,pre); head->left=pre; pre->right=head; return head; } void dfs(Node*root,Node*&head,Node*&pre){ if(!root) return ; dfs(root->left,head,pre); if(!head){ head=root; pre=root; } else{ pre->right=root; root->left=pre; pre=root; } dfs(root->right,head,pre); }
|
解法2
大体和上面一样递归,但是递归的时候没有保存头节点,而是在把节点指针顺序改变好之后(实际上这个时候双链表已经建好了)通过链表的反向遍历找到头节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| Node*pre=NULL; Node* treeToDoublyList(Node* root) { if(!root) return root; dfs(root); auto head=pre; while(head&&head->left) head=head->left; head->left=pre; pre->right=head; return head; } void dfs(Node*root){ if(!root) return ; dfs(root->left); root->left=pre; if(pre) pre->right=root; pre=root; dfs(root->right); }
|
解法3 利用栈非递归中序遍历
二叉搜索树的中序遍历后结果是一个有序数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| Node* treeToDoublyList(Node* root) { if(!root) return root; stack<Node*> stk; Node*pre=NULL,*head=NULL; while(root||stk.size()){ while(root){ stk.push(root); root=root->left; } root=stk.top(); stk.pop(); root->left=pre; if(pre) pre->right=root; pre=root; root=root->right; } head=pre; while(head&&head->left) head=head->left; head->left=pre; pre->right=head; return head; }
|