剑指offer——二叉搜索树与双向链表剑指offer

剑指offer——二叉搜索树与双向链表 1 题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
2 利用非递归 2.1 经典编码：利用中序遍历打印二叉搜索树

package com.offer; import java.util.Stack; class TreeNode{ int val=0; TreeNode left=null; TreeNode right=null; TreeNode(int val){ this.val=val; } } public class PrintBST{ public static void printBST(TreeNode root){ if(root==null){ return; } Stack stack=new Stack(); TreeNode p=root; TreeNode pre=null; while(p!=null || !stack.isEmpty()){ while(p!=null){ stack.push(p); p=p.left; } p=stack.pop(); System.out.print(p.val +" → "); p=p.right; } } public static void main(String[] args){ TreeNode root=new TreeNode(5); TreeNode node2=new TreeNode(3); TreeNode node3=new TreeNode(9); TreeNode node4=new TreeNode(1); TreeNode node5=new TreeNode(4); TreeNode node6=new TreeNode(8); TreeNode node7=new TreeNode(10); root.left=node2; root.right=node3; node2.left=node4; node2.right=node5; node3.left=node6; node3.right=node7; printBST(root); } }

2.2 非递归中序遍历实现题目要求 【剑指offer——二叉搜索树与双向链表】非递归时借助栈实现递归效果，因为栈具有先进后出的特性，具有“记忆”！一般做法均是用栈实现递归！

import java.util.Stack; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }} public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null){ return null; } if(pRootOfTree.left==null && pRootOfTree.right==null){ return pRootOfTree; } Stack stack = new Stack(); TreeNode p = pRootOfTree; TreeNode pre=null; //用于保存中序遍历时的上一个节点 boolean target=true; //判断是否是第一次遍历，用于设置根节点，即数组第一个元素 while(p != null || !stack.isEmpty()){ while(p!=null){ stack.push(p); p=p.left; }//走到最左侧 p=stack.pop(); //第一次循环为最左侧元素出栈 if(target){ pRootOfTree=p; //将中序遍历的第一个节点记为pRootOfTree，最后返回 pre=pRootOfTree; target=false; }else{ pre.right=p; p.left=pre; pre = p; } p=p.right; } return pRootOfTree; } }

3 利用递归 3.1 经典编码：利用中序遍历打印二叉搜索树

package com.offer; class TreeNode{ int val=0; TreeNode left=null; TreeNode right=null; TreeNode(int val){ this.val=val; } } public class PrintBST{ public static void printBST(TreeNode root){ if(root==null){ return; } if(root!=null){//注意此处不能用while，不然会无限循环，输出最左侧节点1！ printBST(root.left); System.out.print(root.val+" → "); printBST(root.right); } }public static void main(String[] args){ TreeNode root=new TreeNode(5); TreeNode node2=new TreeNode(3); TreeNode node3=new TreeNode(9); TreeNode node4=new TreeNode(1); TreeNode node5=new TreeNode(4); TreeNode node6=new TreeNode(8); TreeNode node7=new TreeNode(10); root.left=node2; root.right=node3; node2.left=node4; node2.right=node5; node3.left=node6; node3.right=node7; printBST(root); } }

3.2 递归中序遍历实现题目要求

class TreeNode{ int val=0; TreeNode left=null; TreeNode right=null; TreeNode(int val){ this.val=val; } } public class Solution{ public TreeNode Convert(TreeNode pRootOfTree){ if(pRootOfTree==null){ return null; } if(pRootOfTree.left==null && pRootOfTree.right==null){ return pRootOfTree; } // 1.将左子树构造成双链表，并返回链表头节点 TreeNode left=Convert(pRootOfTree.left); TreeNode p=left; // 2.定位至左子树双链表最后一个节点 while(p != null && p.right != null){ p=p.right; } // 3.如果左子树链表不为空的话，将当前root追加到左子树链表 if(left!=null){ p.right=pRootOfTree; pRootOfTree.left=p; } // 4.将右子树构造成双链表，并返回链表头节点 TreeNode right=Convert(pRootOfTree.right); // 5.如果右子树链表不为空的话，将该链表追加到root节点之后 if(right!=null){ right.left=pRootOfTree; pRootOfTree.right=right; } return left!=null? left : pRootOfTree; } }