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

By AverageJoeWang
 标签:

二叉搜索树与双向链表

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

  • 解题思路
    直接用中序遍历

  • 代码实现
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.Stack;
public class Solution {
    public  TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
             return null;
         } 
       TreeNode node=pRootOfTree;
             Stack<TreeNode> stack=new Stack<TreeNode>();
                Connection(node,stack);

             node=stack.get(0);
             return node;
         }

   public  void Connection(TreeNode newNode,Stack<TreeNode> stack){
            if(newNode==null) {
                return;
            }
             Connection(newNode.left,stack);

             if(stack.isEmpty()){
                 stack.push(newNode);

             }
             else{
                    stack.peek().right=newNode;
                    newNode.left=stack.peek();
                 stack.push(newNode);

             }

             Connection(newNode.right,stack);

         }
}