算法:二叉搜索树与双向链表

二叉搜索树与双向链表

二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

分析

其实对于BST的中序遍历就是有序的了;

而针对双向链表的操作可以参考类似于链表翻转的过程: 从尾到头打印链表

代码

import java.util.Stack;

public class Solution {
    public TreeNode Convert(TreeNode root) {
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, pre = null;
        boolean first = true;
        // 中序遍历
        while (!stack.isEmpty() || cur != null) {
            // 左节点DFS
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 中序遍历
            cur = stack.pop();
            // 头结点处理
            if (first) {
                root = cur;
                pre = root;
                first = false;
                // 中间节点处理
            } else {
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            cur = cur.right;
        }
        return root;
    }
}