首页 > 其他 > 详细

二叉搜索树与双向链表

时间:2018-08-14 14:14:27      阅读:261      评论:0      收藏:0      [点我收藏+]

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
 
 
核心:利用中序遍历的结果有序的性质,遍历出有序的序列,然后对每个序列将left设置为前一个结点,将right设置为后一个结点
          (重点掌握二叉树的遍历递归过程和步骤逻辑)
 1 /**
 2 public class TreeNode {
 3     int val = 0;
 4     TreeNode left = null;
 5     TreeNode right = null;
 6 
 7     public TreeNode(int val) {
 8         this.val = val;
 9 
10     }
11 
12 }
13 */
14 
15 
16 public class Solution {
17 
18     TreeNode head = null;
19     TreeNode res = null;
20 
21     public TreeNode Convert(TreeNode TreeNode) {
22         
23         InOrder(TreeNode);
24         return res;
25 
26          
27 
28     }
29 
30     private void InOrder(TreeNode treeNode) {
31 
32         if (treeNode != null) {
33 
34             InOrder(treeNode.left);
35 
36             if (head == null) {
37 
38                 head = treeNode;
39                 res = treeNode;
40 
41             } else {
42                
43                 head.right=treeNode;
44                 treeNode.left=head;
45                 head=treeNode;
46                 
47                 
48             }
49            InOrder(treeNode.right);
50         }
51 
52     }
53 
54 }

 

二叉搜索树与双向链表

原文:https://www.cnblogs.com/Octopus-22/p/9473656.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!