程序员人生网站导航

二叉搜索树与双向链表

栏目：php教程时间：2016-07-08 16:12:13

题目

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

解题

这里写图片描述

这里写图片描述
根据上图可以发现是中序遍历的进程
但是我们需要改变其结点关系
中序遍历：左根右
调剂后:
root.left = ListLeft
ListLeft.right = root

root.right = ListRight
ListRight.left = root
下面程序为了返回值就是头节点，所有先遍历右子树，后调剂结点，最后遍历左子树。

public class Solution {
    TreeNode list = null;
    public TreeNode Convert(TreeNode pNode){
        if(pNode ==null)
            return pNode;
        TreeNode pCur = pNode;
        if(pCur.right!=null)
            Convert(pCur.right);
        pCur.right = list;
        if(list!=null)
            list.left = pCur;
        list = pCur;
        if(pCur.left!=null)
            Convert(pCur.left);
        return list;
    }
}

讨论中左根右递归程序

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

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

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        if(root.left==null&&root.right==null)
            return root;
        TreeNode left=Convert(root.left);// 最左结点，头结点
        TreeNode tmpLeft=left; // 找到最右结点
        while(tmpLeft!=null&&tmpLeft.right!=null){
            tmpLeft=tmpLeft.right;
        }
        if(left!=null){// 调剂
         tmpLeft.right=root;
         root.left=tmpLeft;
        }
       TreeNode right=Convert(root.right);
        if(right!=null){
            root.right=right;
            right.left=root;
        }

        return  left!=null?left:root; 
    }
}

------分隔线----------------------------

上一篇 这里有一份面筋请查收（一）

下一篇 windows客户端开发--监测windows某一服务是否开启

------分隔线----------------------------