【剑指Offer】026——二叉搜索树与双向链表（树、链表）

题目描述

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

解题思路

题目可能比较难理解，可以看如下的图，我们有一棵二叉搜索树，要求得右边的双向链表。

在二叉搜索树中，左子结点的值总是小于父结点的值，右子节点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子节点的指针调整为链表中指向后一个结点的指针。由于要求链表是有序的，可以借助二叉树中序遍历，因为中序遍历算法的特点就是从小到大访问结点。当遍历访问到根结点时，假设根结点的左侧已经处理好，只需将根结点与上次访问的最近结点（左子树中最大值结点）的指针连接好即可。进而更新当前链表的最后一个结点指针。同时中序遍历过程正好是转换成链表的过程，可采用递归方法处理。

参考代码

Java

import java.util.Stack;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
// 递归法
public class Solution {
    TreeNode head = null;
    TreeNode end = null;  // 一直保存前一个结点
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree); // 中序遍历
        return head;
    }
    public void ConvertSub(TreeNode pRootOfTree){
        if(pRootOfTree == null) return;
        Convert(pRootOfTree.left); // 先遍历左子树，可以想到到最左边的叶节点
        if(end == null){           // 创建head、end为空，到达叶节点
            head = pRootOfTree;
            end = pRootOfTree;
        }else{
            end.right = pRootOfTree;  // 上一个结点指向右边
            pRootOfTree.left = end;   // 新的结点指向前一个结点
            end = pRootOfTree;        // 双向链表向右走
        }
        Convert(pRootOfTree.right);
    }
    // 非递归法
    public TreeNode Convert(TreeNode pRootOfTree) {
        TreeNode head = null;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>(); // 辅助
        while (pRootOfTree != null || !stack.isEmpty()) {
            // left到最左边结点，也解决右子树含有左子树的情况
            while (pRootOfTree != null){ 
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = stack.pop(); // 弹出最左边结点，也就是头节点
            if(head == null){   // 创建head、end为空，到达叶节点
                head = pRootOfTree;
                pre = pRootOfTree;
            }else{
                pre.right = pRootOfTree; // 前一个结点指向右边
                pRootOfTree.left = pre;  // 当前结点指向前一个杰作（左）
                pre = pRootOfTree;       // 更新前一个结点
            }
            pRootOfTree = pRootOfTree.right; // 右子树
        }
        return head;
    }
}

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.head, self.end = None, None
    def Convert(self, pRootOfTree):
        # write code here
        self.ConvertSub(pRootOfTree)
        return self.head
    def ConvertSub(self, pRootOfTree):
        if not pRootOfTree:
            return
        self.Convert(pRootOfTree.left)
        if not self.end:
            self.head = pRootOfTree
            self.end = pRootOfTree
        else:
            self.end.right = pRootOfTree
            pRootOfTree.left = self.end
            self.end = pRootOfTree
        self.Convert(pRootOfTree.right)

个人订阅号