牛客--剑指offer-二叉搜索树和双向链表

一、问题描述

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

二、解题思路

将二叉搜索树转换成双向链表，其实就是按照中序遍历的方式来遍历二叉树然后建立链表，可以分为递归和非递归两种方式来解决：

1.递归方式

递归方式，因为每次递归返回的是链表的头节点，而添加新元素是在链表的尾部，而当前递归返回的又是链表的头节点，因此需要不断左右遍历链表。

2.非递归方式

利用栈空间来解决，定义两个TreeNode,一个指向链表的头节点，另一个指向链表的当前节点位置。

三、代码

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 { //TreeNode root=null; public TreeNode Convert(TreeNode pRootOfTree) { //非递归方式求解 if(pRootOfTree==null) return pRootOfTree; Stack<TreeNode> stack=new Stack<TreeNode>(); TreeNode result=null;//用来存储双向链表的头节点 TreeNode cur=null;//用来存储链表的当前操作节点 while(!stack.empty() || pRootOfTree!=null){ while(pRootOfTree!=null){ stack.push(pRootOfTree); pRootOfTree=pRootOfTree.left; } if(!stack.empty()){ TreeNode tmp=stack.pop(); if(result==null){ result=tmp; cur=result; }else{ cur.right=tmp; tmp.left=cur; cur=cur.right; } pRootOfTree=tmp.right; } } return result; /*以下为递归方式求解 if(pRootOfTree==null) return pRootOfTree; // if(pRootOfTree.left==null && root==null){ // root=pRootOfTree; // return pRootOfTree; // }else if(pRootOfTree.left==null && root!=null) // return pRootOfTree; TreeNode left; TreeNode right; if(pRootOfTree.left==null)//如果当前节点的左节点为空，left指向当前节点 left=pRootOfTree; else{ //如果当前节点不为空，递归 left=Convert(pRootOfTree.left); //因为返回的是链表的头节点，需要找到尾节点，然后添加pRootOfTree到当前链表 while(left!=null && left.right!=null) left=left.right; left.right=pRootOfTree; pRootOfTree.left=left; left=left.right; } if(pRootOfTree.right==null){ while(left!=null && left.left!=null) left=left.left; return left; } right=Convert(pRootOfTree.right); left.right=right; right.left=left; while(left!=null && left.left!=null) left=left.left; return left; */ } }

下面是使用递归的方式重新实现的

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { TreeNode head = null; public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree == null) return null; TreeNode result = convertCore(pRootOfTree); while(result.left != null) result = result.left; return result; } private TreeNode convertCore(TreeNode root){ if(root == null){ return null; } TreeNode left = convertCore(root.left); TreeNode right = convertCore(root.right); if(left != null){ while(left.right!=null){ left = left.right; } left.right = root; root.left = left; } if(right != null){ while(right.left != null) right = right.left; right.left = root; root.right = right; } return root; } }