二叉搜索树与双向链表
二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解法
由于是二叉搜索树，因此中序遍历的结果就是排序的。
中序遍历利用栈来实现。遍历时，前一个结点的 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;
}
}
测试用例
- 功能测试（输入的二叉树是完全二叉树；所有结点都没有左/右子树；只有一个结点的二叉树）；
- 特殊输入测试（指向二叉树根结点的指针为空指针）。
