每日算法之二叉搜索树与双向链表

每日算法之二叉搜索树与双向链表

JZ36 二叉搜索树与双向链表

描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表
注意:
1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构
4.你不用输出双向链表,程序会根据你的返回值自动打印输出

思路:

二叉树中序遍历除了递归方法,我们还可以尝试非递归解法,与常规的非递归中序遍历几乎相同,还是借助栈来辅助,只是增加了连接节点。

具体做法:

step 1:创建两个指针,一个指向题目中要求的链表头(head),一个指向当前遍历的前一节点(pre),创建一个布尔型变量,标记是否是第一次到最左,因为第一次到最左就是链表头。
step 2:判断空树不能连接。
step 3:初始化一个栈辅助中序遍历。
step 4:依次将父节点加入栈中,直接进入二叉树最左端。
step 5:第一次进入最左,初始化head与pre,然后进入它的根节点开始连接。
step 6:最后将右子树加入栈中,栈中依次就弹出“左中右”的节点顺序,直到栈为空。

代码

package mid.JZ36二叉搜索树与双向链表;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
public class Solution {

    //头节点
    private TreeNode head = null;

    //上一个节点
    private TreeNode pre = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        //首先递归到最左最小值
        Convert(pRootOfTree.left);

        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            pRootOfTree.left = pre;
            pre.right = pRootOfTree;
            pre = pRootOfTree;
        }
        //右递归
        Convert(pRootOfTree.right);
        return head;
    }
}

原文地址:https://www.cnblogs.com/loongnuts/archive/2022/12/08/16965602.html