二叉搜索树与双向链表

清疚 2022-03-25 15:37 177阅读 0赞

# [二叉搜索树与双向链表][Link 1] #

## 题目描述 ##

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

核心：利用中序遍历的结果有序的性质，遍历出有序的序列，然后对每个序列将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 }

posted @ 2018-08-14 11:41 [Octopus22][] 阅读( ...) 评论( ...) [编辑][Link 2] 收藏

[Link 1]: https://www.cnblogs.com/Octopus-22/p/9473656.html
[Octopus22]: https://www.cnblogs.com/Octopus-22/
[Link 2]: https://i.cnblogs.com/EditPosts.aspx?postid=9473656