题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
分析：将二叉搜索树转换成一个排序的双向链表，即在对二叉搜索进行中序遍历时，将节点指向左子树的指针指向中序遍历的前一个节点，将节点指向右子节点的指针指向中序遍历的下一个节点。需要注意的是左子树的最右节点，右子树的最左节点。代码如下：
1 /**
2 public class TreeNode {
3 int val = 0;
4 TreeNode left = null;
5 TreeNode right = null;
6
7 public TreeNode(int val) {
8 this.val = val;
9
10 }
11
12 }
13 */
14 public class Solution {
15 TreeNode tail =
null ;
16 public TreeNode Convert(TreeNode pRootOfTree) {
17 convertNode(pRootOfTree);
18 TreeNode head =
tail ;
19 while(head!=
null&&head.left!=
null){
20 head =
head.left;
21 }
22 return head ;
23 }
24 private void convertNode(TreeNode node) {
25 if(node==
null){
26 return ;
27 }
28 TreeNode current =
node ;
29 if(current.left!=
null){
30 convertNode(current.left);
31 }
32 current.left =
tail ;
33 if(tail!=
null){
34 tail.right=
current ;
35 }
36 tail =
current ;
37 if(current.right!=
null){
38 convertNode(current.right);
39 }
40 }
41 }
转载于:https://www.cnblogs.com/huntertoung/p/4801102.html
