网站建设单元格边距,网站制作价钱多少,北京公司建站模板,各大高校的校园网站建设题目
输入一棵二叉搜索树#xff0c;将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围#xff1a;输入二叉树的节点数 0≤n≤1000#xff0c;二叉树中每个节点的值 0≤val≤1000 要求#xff1a;O(1)#xff08;即在原树上操作#xff09;#xff0c;时间…题目
输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围输入二叉树的节点数 0≤n≤1000二叉树中每个节点的值 0≤val≤1000 要求O(1)即在原树上操作时间复杂度 O(n)
注意:
1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构
4.你不用输出双向链表程序会根据你的返回值自动打印输出
输入描述
二叉树的根节点
返回值描述
双向链表的其中一个头节点。
示例1
输入{10,6,14,4,8,12,16}
返回值From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明输入题面图中二叉树输出的时候将双向链表的头节点返回即可。
示例2
输入{5,4,#,3,#,2,#,1}
返回值From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明 5/4/3/2/1
树的形状如上图 解答
源代码
import java.util.*;
/**
public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;}}
*/
public class Solution {public TreeNode pre null;public TreeNode head null;public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree null) {return null;}Convert(pRootOfTree.left);if (pre null){pre pRootOfTree;head pRootOfTree;} else {pre.right pRootOfTree;pRootOfTree.left pre;pre pRootOfTree;}Convert(pRootOfTree.right);return head;}
}总结
二叉搜索树按中序遍历就可以得到一个从小到大排列的序列因此可以通过对二叉树进行中序遍历来得到双向链表。head保存头结点pre保存上一个结点连接好当前节点和pre后将pre设置为当前结点。
