题目简述
- 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
- 要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路分析：
- 通过中序遍历序列，将二叉树变成有序的双向链表，将树型结构转化成线性结构。
- 中序遍历，left指向前节点right指向后节点
- 遍历过程中，需要调整所左右节点指针。
递归版
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == nullptr) return nullptr;// 特殊情况处理
TreeNode* pre = nullptr; // 辅助前节点
convertHelper(pRootOfTree, pre);// 递归转换
TreeNode* res = pRootOfTree;
while(res->left) // 向前遍历，找到头节点
res = res->left;
return res; // 返回头指针
}
/**
cur 当前节点、pre 前一个节点
*/
void convertHelper(TreeNode* cur, TreeNode* &pre)
{
// 递归退出
if(cur == nullptr) return;
convertHelper(cur ->left, pre); // 递归遍历左子树
// 二叉树转换
cur->left = pre;
// 当前前驱节点不为空
if(pre) pre->right = cur;
// 更新前驱节点为当前节点
pre = cur;
convertHelper(cur ->right, pre);// 递归遍历右子树
}
};
非递归版
// 非递归版
// 解题思路：
// 1.核心是中序遍历的非递归算法。
// 2.修改当前遍历节点与前一遍历节点的指针指向。
import java.util.Stack;
public TreeNode ConvertBSTToBiList(TreeNode root) {
if(root==null)
return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
TreeNode pre = null;// 用于保存中序遍历序列的上一节点
boolean isFirst = true;// 首节点处理辅助变量
while(p!=null||!stack.isEmpty()) {// 巧妙的处理了子叶节点和之前存储的祖先节点
while(p!=null){// 节点不为空
stack.push(p); // 入栈
p = p.left;// 向左走
}
p = stack.pop();// 最左出栈
if(isFirst){ //首节点处理
root = p;// 将中序遍历序列中的第一个节点记为root
pre = root;
isFirst = false;
}else{ //中间节点处理，执行转换操作
pre.right = p;// 右子树更新为中序遍历后继节点
p.left = pre;// 左子树更新为中序遍历前继节点
pre = p;// 更新前节点
}
p = p.right;// 获取右子树
}
return root;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
