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


题目描述

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

解法

由于是二叉搜索树,因此中序遍历的结果就是排序的。

中序遍历利用栈来实现。遍历时,前一个结点的 right 指向后一个结点,后一个结点的 left 指向前一个结点。

pre.right = cur
cur.left = pre
import java.util.Stack;

/**
 * @author bingo
 * @since 2018/11/24
 */

/**
 public class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
 this.val = val;

 }

 }
 */
public class Solution {
    /**
     * 将二叉搜索树转换为双向链表
     *
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = pRootOfTree;
        TreeNode res = null;
        TreeNode pre = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (pre == null) {
                    pre = cur;
                    res = pre;
                } else {
                    pre.right = cur;
                    cur.left = pre;
                    pre = cur;
                }
                cur = cur.right;

            }
        }
        return res;
    }
}

测试用例

  1. 功能测试(输入的二叉树是完全二叉树;所有结点都没有左/右子树;只有一个结点的二叉树);
  2. 特殊输入测试(指向二叉树根结点的指针为空指针)。