剑指Offer-二叉搜索树与双向链表

我会带着你远行 2022-02-25 10:08 141阅读 0赞

## 题目描述 ##

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

解题思路—**递归**：抓住**二叉搜索树**的本质，可以使用**中序遍历**进行排序。将左子树构造成双链表，然后再递归右子树。注意：递归时一定要判断当前结点是否为null。  
解题思路—**递归精简版**：这个代码更精简，使用全局变量一直跟踪递归到的左子树结点，非常简洁明了。**推荐！**  
解题思路—**非递归堆栈版**：如果不使用递归，可以使用堆栈来保存之前的节点，核心思想还是使用中序遍历，但是使用堆栈编写代码较为繁琐，没有递归简洁。

## Java解题—递归 ##

public class Solution {
        TreeNode head = null;
        TreeNode returnhead = null;
        public TreeNode Convert(TreeNode pRootOfTree) {
            PostOrder(pRootOfTree);
            return returnhead;
        }
        
        public void PostOrder(TreeNode root){
            if(root==null) return;
            PostOrder(root.left);
            if(head==null){
                head = root;
                returnhead = root;
            }else{
                head.right = root;
                root.left = head;
                head = root;
            }
            PostOrder(root.right);
        }
    }

## Java解题—递归精简版 ##

public class Solution {
        TreeNode pre = null;
        TreeNode returnhead = null;
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree==null)
                return null;
            Convert(pRootOfTree.left);
            pRootOfTree.left = pre;
            if(pre!=null)
                pre.right = pRootOfTree;
            pre = pRootOfTree;
            // 确认返回的头结点
            returnhead = returnhead==null?pRootOfTree:returnhead;
            Convert(pRootOfTree.right);
            return returnhead;
        }
    }

## Java解题—非递归（使用堆栈） ##

import java.util.Stack;
    public class Solution {
        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;
        }
    }