剑指Offer_26

发表于 | 分类于

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解题思路

递归实现，从链表的头部开始直到链表的尾部，即从BST的最左子树节点出发，到最右子树的节点

因为从子树节点递归返回到父节点，父节点是不是它的前作为当前链表的节点，并不清楚他的前节点应该左子树节点，右子树节点或者是空节点，所以设置了全局变量pre来作为先前节点。

在ConverHelper中，二叉树的中序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private TreeNode pre = null;
    
    private void ConvertHelper(TreeNode cur){
        if(cur == null){
            return;
        }
        ConvertHelper(cur.left);
        
        //设置双端指针
        cur.left = pre;
        if(pre != null){
            pre.right = cur;
        }
        pre = cur;
        
        ConvertHelper(cur.right);
    }
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        ConvertHelper(pRootOfTree);
        TreeNode pHead = pRootOfTree;
	
		//找链表的头结点
        while(pHead.left != null){
            pHead = pHead.left;
        }
        return pHead;
    }
}