面试题36 二叉搜索树与双向链表

题目描述

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

题解

题目要求排序的双向链表，则：

1. 采用中序遍历，刚好节点的值为一个递增的序列。
2. 双向链表： 则链表中相邻的两个节点之间（如果驱节点 pre ，当前节点 cur）有则 pre.right = cur， cur.left = pre

算法流程

采用非递归的中序dfs，用一个栈记录访问次序，一个辅助链表记录访问结果，在辅助链表中修改指针指向。返回辅助链表的第一个节点；

复杂度分析：
时间复杂度 O(N) ： N 为二叉树的节点数，中序遍历需要访问所有节点。
空间复杂度 O(N) ： 辅助链表res使用 O(N)空间。辅助栈stack最差情况下也是O(N)空间。

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        if(pRootOfTree.left == null && pRootOfTree.right == null) return pRootOfTree;
        ArrayList<TreeNode> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode temp = pRootOfTree;

        // 形成一个中序遍历的结果，并添加指针。
        while(!stack.empty() || temp != null){
            if(temp != null){
                stack.add(temp);
                temp = temp.left;
            }else{
                temp = stack.pop();
                res.add(temp);
                temp = temp.right;
            }
        }
        // 修改链表指针指向。
        for(int i = 0; i < res.size()-1; i++){
            res.get(i+1).left = res.get(i);
            res.get(i).right = res.get(i+1);
        }
        return res.get(0);
    }
}

递归写法：
时间复杂度 O(N) ： N 为二叉树的节点数，中序遍历需要访问所有节点。
空间复杂度 O(N) ： 当二叉树退化为链表时，递归辅助栈最差情况下也是O(N)空间。

public class Solution {
    TreeNode head = null; 
    TreeNode  pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        dfs(pRootOfTree);
        return head;
    }
    void dfs(TreeNode cur){
        if(cur == null) return ;
        dfs(cur.left);
        if(pre != null) pre.right = cur;  // 一般情况
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}