首页 > 代码库 > 剑指Offer之二叉搜索树与双向链表
剑指Offer之二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
基本思路
假设二叉搜索树为{10,6,14,4,8,12,16}，按照中序遍历，当我们遍历转换到根节点（值为10的节点）时，它的左子树已经转换成一个排序的链表了，并且处在链表的最后一个节点是当前最大的节点。我们把值为8的节点和根节点链接起来，此时链表中的最后一个节点就是10了。接着我们去遍历转换右子树，并把根节点和右子树的最小的节点链接起来。转换左子树和右子树，使用递归的方法。
Java代码
package com.swordOffer.convertBinarySearchTree18;/** * Created by Feng on 2017/5/15. * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。 */public class ConvertBinarySearchTree { public static void main(String[] args) { TreeNode node1 = new TreeNode(10); TreeNode node2 = new TreeNode(6); TreeNode node3 = new TreeNode(14); TreeNode node4 = new TreeNode(4); TreeNode node5 = new TreeNode(8); node1.left = node2; node1.right = node3; node2.left = node4; node2.right = node5; TreeNode result = convertNode(node1); System.out.println(result.val); } public static TreeNode convertNode(TreeNode pRootOfTree) { //如果根节点为空,返回空 if (pRootOfTree == null) { return null; } //如果只有根节点 if (pRootOfTree.left == null && pRootOfTree.right == null) { return pRootOfTree; } //转换左子树 TreeNode pLeft = convertNode(pRootOfTree.left); TreeNode pNode = pLeft; while (pNode != null && pNode.right != null) { pNode = pNode.right; } if (pLeft != null) { pNode.right = pRootOfTree; pRootOfTree.left = pNode; } //转换右子树 TreeNode pRight = convertNode(pRootOfTree.right); if (pRight != null) { pRootOfTree.right = pRight; pRight.left = pRootOfTree; } return pLeft != null ? pLeft : pRootOfTree; }}class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}
剑指Offer之二叉搜索树与双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。