二叉搜索树与双向链表

 /* 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。*/
           //核心是中序遍历的非递归算法。
           if(pRootOfTree == null)  //如果树节点为空,则返回为空
               return null;
         TreeNode p = pRootOfTree;  
         boolean isFirst = true;    //因为头节点需要差别对待,所以设置标志位
         TreeNode pre = null;
         Stack<TreeNode> s1 = new Stack<>();
         while( p != null || !s1.isEmpty()) {         //p是遍历的每个节点,然后复制给pre,然后遍历下一个,所以只要p不为空,就要接着遍历     
                                                      //s1堆栈中存放的是每一个子树的根节点,当遍历之后,堆栈为空,如果没有遍历完,那就接着在循环里面
             while( p != null) {                      //如果p为空这表示这棵子树的左右节点为空了。此时不进入循环而是进入上一个级别的子树,
                 s1.push(p);                          //如果p不为空,则找到最左端的子节点并不断把上一级的节点压栈
                 p = p.left;
             }
             p = s1.pop();                            //弹出使得p指向上一个级别的子树
             if(isFirst) {
                 pRootOfTree = p;                    //如果是头节点的话,则将p赋值给头结点
                 pre = pRootOfTree;                  //pre的作用是表示前一级的节点
                 isFirst = false;
             }else {
                 pre.right = p;                      //和前一级的节点建立连接
                 p.left = pre;
                 pre = p;
             }
             p = p.right;                            //这个就是理解的重点了,如果p已经是叶子节点,则p为空,下一个循环不需要压栈元素,而是接受弹栈的节点,上一级
                                                     //弹栈的节点即是其根节点。如果其存在右子树,则是已经遍历了左节点和根节点以后,那么指向右子树,那可以把右子树
                                                     //当做一个新树对待进行遍历,当期整个树遍历完,则会接受新的弹栈节点,接着进行遍历。所以这就是利用栈的优点。
                                                      //看似没有使用递归,但是还是在用递归的思维
         }
        return pRootOfTree;

    原文作者:ZWB626
    原文地址: https://blog.csdn.net/ZWB626/article/details/84205970
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞