[每日一道小算法（三十七）] [二叉搜索树] [链表] 二叉搜索树转换为双向链表（剑指offer）

刺骨的言语ヽ痛彻心扉 2023-07-06 06:16 22阅读 0赞

前言：  
递归虐我千万遍，我待递归如初恋！！！！！！

### 题目描述 ###

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

### 解题思路 ###

这道题刚拿出来时，真的一点思路没有。那就一点一点的分解分析吧。首先分析二叉搜索树。他有什么可以使用的知识点呢。所有左子树都大于小于根节点的值，所有的右子树都大于等于根节点的值。所有排序我们可以使用中序遍历来完成，因为中序遍历后的顺序就是按照大小顺序排列的。我们再来看双向链表，有双向指针。所以我们可以把树中的左指针当作指向链表的前一节点指针，把右指针当作指向链表的后一节点的指针。  
这道题用了两种方法来实现，第一种方法使用一个数组，保存中序遍历的数组，然后在进行指针转换。  
第二种方法直接在递归的时候就转换指针。

### 代码样例 ###

#### 方法一（数组存储） ####

package com.asong.leetcode.TreeNodeList;
    
    import Combination.Tree;
    
    import java.lang.reflect.Array;
    import java.util.ArrayList;
    
    /** * 二叉搜索树变为双向链表 */
    public class Solution1 { 
        public TreeNode Convert(TreeNode pRootOfTree)
        { 
            if(pRootOfTree==null)
            { 
                return null;
            }
            ArrayList<TreeNode> list = new ArrayList<TreeNode>();
            Middle(pRootOfTree,list);
            return ListConvert(list);
        }
    
        //中序遍历，保存到list中
        public static void Middle(TreeNode pRoot,ArrayList<TreeNode> list)
        { 
            if(pRoot.left!=null)
            { 
                Middle(pRoot.left,list);
            }
            list.add(pRoot);
            if(pRoot.right!=null)
            { 
                Middle(pRoot.right,list);
            }
        }
        //进行指针转换
        public static TreeNode ListConvert(ArrayList<TreeNode> list)
        { 
            for (int i = 0; i < list.size()-1; i++) { 
                list.get(i).right = list.get(i+1);
                list.get(i+1).left = list.get(i);
            }
            return list.get(0);
        }
    }

#### 方法二（递归，直接指针转换） ####

package com.asong.leetcode.TreeNodeList;
    
    /** * 二叉搜索树变成双向链表 */
    public class Solution { 
        static TreeNode nodeList = null;
        public static TreeNode Convert(TreeNode pRootOfTree) { 
            //中序遍历时就改变指针方向
            inOrderConvert(pRootOfTree);
            //寻找链表表头
            while(nodeList!=null && nodeList.left!=null)
            { 
                nodeList = nodeList.left;
            }
            return nodeList;
        }
        //中序遍历并改变指针
        public static void inOrderConvert(TreeNode root)
        { 
            if(root == null)
            { 
                return;
            }
            if(root!=null)
            { 
                inOrderConvert(root.left);
                root.left = nodeList;
                if(nodeList!=null)
                { 
                    nodeList.right = root;
                }
                nodeList = root;
                inOrderConvert(root.right);
            }
        }
    
        public static void main(String[] args) { 
            TreeNode root = new TreeNode(10);
            root.left = new TreeNode(6);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(8);
            root.right = new TreeNode(14);
            root.right.left = new TreeNode(12);
            root.right.right = new TreeNode(16);
            TreeNode pRoot = Convert(root);
    
        }
    }