剑指offer-26-二叉搜索树转双向链表

二叉搜索树与双向链表

http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5

思路

二叉搜索树的特点是左<根<右

  • 中序遍历结点,用一个数组或者队列存储中序遍历的顺序
  • 线索二叉树,比当前结点小的结点中的最大结点是当前结点的前驱结点,相应的另外一个就是后继结点,所以这题就是找到每一个结点的前驱和后继节点,其实就是线索二叉树了

代码

中序遍历

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
import java.util.*;
public class Solution {
    ArrayList<TreeNode> arr=new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){return pRootOfTree;}
        mid(pRootOfTree);
        TreeNode head=arr.get(0);
        for(int i=0;i<arr.size()-1;i++){
            arr.get(i+1).left=arr.get(i);
            arr.get(i).right=arr.get(i+1);

        }
        arr.get(0).left=null;
        arr.get(arr.size()-1).right=null;
        return head;
    }

    public void mid(TreeNode root){
        if(root==null){
            return;
        }
        mid(root.left);
        arr.add(root);
        mid(root.right);
    }

}
剑指offer与数据结构 文章被收录于专栏

本专栏包括剑指offer题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构

全部评论

相关推荐

北漂的牛马人:211佬,包进的,可能是系统问题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务