[名企面试知识点][Java]二叉搜索树与双向链表
发布于 2017-03-14 14:05 1578 次浏览 0 赞 来自 笔试面试  

题目描述

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

输入描述

二叉搜索树

输出描述

排序的双向链表

题目分析

节点描述:

public class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;

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

   }

}

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  • 任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

  • 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

  • 任意节点的左、右子树也分别为二叉查找树;

  • 没有键值相等的节点。

解法一(递归) 运行时间:32ms 占用内存:550k

//递归调用 左 根 右 遍历
public class Solution {
    //双向链表的左边头结点和右边头节点
   TreeNode leftHead = null;
   TreeNode rightHead = null;
   public TreeNode Convert(TreeNode pRootOfTree) {
        //递归调用叶子节点的左右节点返回null
       if(pRootOfTree==null) return null;
        //第一次运行时,它会使最左边叶子节点为链表第一个节点
       Convert(pRootOfTree.left);
       if(rightHead==null){
           leftHead= rightHead = pRootOfTree;
       }else{
           //把根节点插入到双向链表右边,rightHead向后移动
          rightHead.right = pRootOfTree;
          pRootOfTree.left = rightHead;
          rightHead = pRootOfTree;
       }
        //把右叶子节点也插入到双向链表(rightHead已确定,直接插入)
       Convert(pRootOfTree.right);
        //返回左边头结点
       return leftHead;
   }
}

  找到树最左边的叶子节点,以该节点为双向链表的第一个节点,然后根据 左 根 右 遍历依次把节点插入到双向链表右边并移动rightHead指针 ,最后返回leftHead。

解法二 运行时间:31ms 占用内存:503k

import java.util.Stack;
public class Solution {
   public TreeNode Convert(TreeNode pRootOfTree) {
       if(pRootOfTree == null) return pRootOfTree;
       //双向链表的左边头结点和右边头节点
       TreeNode leftHead = null;
       TreeNode rightHead = null;
      Stack<TreeNode> s = new Stack<TreeNode>();
      while(pRootOfTree != null || !s.isEmpty()){
           if(pRootOfTree != null) {
               //依次遍历到最左边叶节点
               s.push(pRootOfTree);
               pRootOfTree = pRootOfTree.left;
           } else {
               pRootOfTree = s.pop();
               if(rightHead == null)
                   //以最左边叶子节点为链表头
                   leftHead = rightHead = pRootOfTree;
               else {
                   rightHead.right = pRootOfTree;
                   pRootOfTree.left = rightHead;
                   rightHead = pRootOfTree;
               }
               pRootOfTree = pRootOfTree.right;
           }
       }

       return leftHead;
   }
}

思路一样,以最左边叶子节点为链表头,借用堆栈遍历链表。

添加回复
回到顶部