题目:二叉搜索树与双向链表

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

 

1一开始我连题目都看不懂,只能想到用中序遍历,但是我不知道该怎么去改中序遍历的代码

2看了大牛的代码,发现我对不能创建任何新的结点有误解,其实可以新建节点eg:TreeNode p = root;但这不是新建,只是新建了节点,指向了这棵树中的某些节点.

而且如果你不建新的指向,这题根本没法做啊

此题中的双向链表可以理解为 1  <---->   2

1.right 为2 

2.left为1

思路一:非递归的方法

 

 1 import java.util.*;
 2 /**
 3 public class TreeNode {
 4     int val = 0;
 5     TreeNode left = null;
 6     TreeNode right = null;
 7     public TreeNode(int val) {
 8         this.val = val;
 9     }
10 }
11 */
12 public class Solution {
13     public TreeNode Convert(TreeNode root) {
14         //考虑特殊情况
15         if(root==null) return null;
16         //中序遍历只需一个指针,指向从堆栈中pop出来的即可.但题目要求是双向链表,所以肯定需要再设置一个指针
17         TreeNode cur = root;
18         TreeNode pre = null;
19         //初始化堆栈
20         Stack<TreeNode> stack = new Stack<TreeNode>();
21         boolean init = true;//在实际过程中,这个true只会用来初始化双向链表的头结点,初始完后的所有过程都是false
22         while( !stack.empty() || cur!= null){
23             //一次入栈,直到最左边的点入栈
24             while(cur!= null){
25                 stack.push(cur);
26                 cur= cur.left;
27             }
28             cur = stack.pop();
29             if(init==true){//对应上方21行代码
30                 root = cur; //赋值给root之后,就不能再对root节点进行操作,因为最终要返回root,防止被覆盖.剩下的用cur和pre节点进行操作
31                 pre = root;
32                 init = false;//初始化后,init也就没用了,设置为false
33             }else{//生成双向链表
34                 pre.right = cur;
35                 cur.left = pre;
36                 pre = cur;
37             }
38             cur= cur.right;
39         }
40         return root;
41     }
42 }

 

思路二:递归的方法(todolist)

本地编译器代码(TODOlist)