精华内容
下载资源
问答
  • 面试题36. 二叉搜索树与双向链表 递归实现 问题:栈溢出: [28,-98,67,null,-89,62,null,-97,-25,null,64,null,null,-72,-9,null,null,-88,-41,null,-7,null,-78,-53,null,null,2,-85,-77,-69,-42,-1] class...

     面试题36. 二叉搜索树与双向链表

    递归实现

    问题:栈溢出:  

    [28,-98,67,null,-89,62,null,-97,-25,null,64,null,null,-72,-9,null,null,-88,-41,null,-7,null,-78,-53,null,null,2,-85,-77,-69,-42,-1]

    
    class Node {
    public:
    	int val;
    	Node* left;
    	Node* right;
    
    	Node() {}
    
    	Node(int _val) {
    		val = _val;
    		left = NULL;
    		right = NULL;
    	}
    
    	Node(int _val, Node* _left, Node* _right) {
    		val = _val;
    		left = _left;
    		right = _right;
    	}
    };
    
    /*
    全局保存头尾指针
    先递归左子树
    连接,并更新尾部指针
    再递归右子树
    */
    
    Node*head = nullptr, *tail = nullptr;
    
    void inOrder(Node*& root) {
    	if (root == nullptr) {
    		return;
    	}
    
    	inOrder(root->left);
    
    	if (head == nullptr) {
    		head = root;
    	}
    
    	if (tail != nullptr) {
    		tail->right = root;
    		root->left = tail;
    	}
    	tail = root;
    
    	inOrder(root->right);
    
    }
    
    Node* treeToDoublyList(Node* root) {
    	if (root == nullptr) {
    		return nullptr;
    	}
    	inOrder(root);
    
    	if (tail&&head) {
    		tail->right = head;
    		head->left = tail;
    	}
    
    	return head;
    
    }
    
    
    Node* buildBST(Node*t,int num) {
    	if (t == nullptr) {
    		t = new Node(num);
    	}
    	else
    	{
    		if (num < t->val) {
    			t->left = buildBST(t->left, num);
    		}
    		else
    		{
    			t->right = buildBST(t->right,num);
    		}
    	}
    	return t;
    }
    
    
    Node* creat() {
    
    	Node* t = nullptr;
    	int n;
    	cin >> n;
    	while (n--)
    	{
    		int num;
    		cin >> num;
    		t=buildBST(t, num);
    	}
    
    	return t;
    
    }
    
    
    int main()
    {
    	Node* root=creat();
    
    	treeToDoublyList(root);
    
    	std::cout << "Hello World!\n";
    }

     栈

    • 将树的左子树依次存入stack
    • 每次pop出一个Node将其右子树的左子树也依次存入stack
    • 饭后做连接操作
    Node* treeToDoublyList(Node* root) {
    	if (root == nullptr) {
    		return nullptr;
    	}
    	Node*cur = root;
    	Node*before = nullptr;
    	Node*after = nullptr;
    	Node*head = nullptr;
    
    
    	stack<Node*> stac;
    
    
    	while (cur){
    		stac.push(cur);
    		head = cur;
    		cur = cur->left;
    	}
    	 
    	while (!stac.empty()) {
    		cur = stac.top();
    		stac.pop();
    		Node*tmp = cur->right;
    		while (tmp) {
    			stac.push(tmp);
    			tmp = tmp->left;
    		}
    
    		if (stac.empty()) {
    			after = head;
    		}
    		else{
    			after = stac.top();
    		}
    
    		cur->left = before;
    		cur->right = after;
    		before = cur;
    
    	}
    	head->left = before;
    
    	return head;
    
    
    }
    

     

     面试题37. 序列化二叉树

    递归

    
    
    
    void preOrder(TreeNode* root, string&res) {
    	if (root) {
    		res += "#,";
    		return;
    	}
    
    	res += to_string(root->val) + ",";
    	preOrder(root->left,res);
    	preOrder(root->right,res);
    }
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
    	string res="";
    	if (root == nullptr) {
    		return res;
    	}
    
    	preOrder(root,res);
    
    	return res;
    }
    TreeNode* preOrderDecode(int& p, const string& data) {
    	if (data[p] == '#') {
    		p += 2;
    		return nullptr;
    	}
    
    	bool is_n = false;
    	if (data[p] == '-') {
    		is_n = true;
    		p++;
    	}
    	int num = 0;
    	while (data[p]!=','){
    		num = num * 10 + (data[p] - '0');
    		p++;
    	}
    	if (is_n) num = -num;
    
    	auto root = new TreeNode(num);
    	root->left = preOrderDecode(p, data);
    	root->right = preOrderDecode(p, data);
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
    	if (data.size() <= 0) {
    		return nullptr;
    	}
    	int p = 0;
    	return preOrderDecode(p,data);
    
    }
    };
    

     

    迭代 层次

     

     

     

     

     

     

     

     

    展开全文
  • 双向链表面试题要求list和node是不同的结构体,所以这里使用的void*指针 1声明LIst和Node结构体 2创建链表 3尾部追加 4头部删除 都很简单,我只写了创建 打印时测试用的,主要就是试试void*类型的...

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<malloc.h>
    using namespace std;
    
    typedef struct mylist
    {
        void* head;
        void* tail;
    } List,*pList;
    
    typedef struct mynode
    {
        void* next;
        void* prev;
        int data;
    } Node,*pNode;
    
    pList createlist()
    {
        pList root;
        pNode temp;
        int n;
        root = (pList)malloc(sizeof(List));
        root->head = NULL;
        root->tail = NULL;
        printf("input data number:");
        scanf("%d",&n);
        if(n&&NULL==root->head)
        {
            temp = (pNode)malloc(sizeof(Node));
            printf("data1:");
            scanf("%d",&temp->data);
            temp->next = (pList)root;
            temp->prev = (pList)root;
            root->head = (pNode)temp;
            root->tail = (pNode)temp;
            n--;
        }
        for(int i=1; i<=n ; i++)
        {
            temp = (pNode)malloc(sizeof(Node));
            printf("data%2d:",i);
            scanf("%d",&temp->data);
            temp->next = (pList)root;
            temp->prev = (pNode)root->tail;
            ((pNode)(root->tail))->next = (pNode)temp;
            root->tail = (pNode)temp;
        }
        return root;
    }
    
    void printlist(pList root)
    {
        pNode temp = (pNode)root->head;
        int i = 1;
        while(temp!=(pNode)root)
        {
            printf("data%2d:%d\n",i++,temp->data);
            temp = (pNode)temp->next;
        }
    
        /*temp = (pNode)root->tail;
        while(temp!=(pNode)root)
        {
            printf("data%2d:%d\n",--i,temp->data);
            temp = (pNode)temp->prev;
        }*/
    }
    
    int main()
    {
        pList root;
        root = createlist();
        printlist(root);
    }
    


    双向链表的面试题要求list和node是不同的结构体,所以这里使用的void*指针

    1声明LIst和Node结构体

    2创建链表

    3尾部追加

    4头部删除

    都很简单,我只写了创建 打印时测试用的,主要就是试试void*类型的指针用法

    上面的所有都加上了显示类型转换

    以下去掉了不必要的类型转换

    总结一下,

    1.当给void*类型指针赋值的时候不需要显示类型转换

    2.void*给void*赋值不需要转换

    3.当void*给其他类型的指针赋值时需要显示类型转换

    4.当void*与不同类型的指针比较的时候需要显示类型转换

    5.当需要链式的时候需要显示类型转换。

    注释标记对应1,2,3,4,5的情况

    注意:不转换不等于不需要转换,而是编译器隐式转换了

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<malloc.h>
    using namespace std;
    
    typedef struct mylist
    {
        void* head;
        void* tail;
    } List,*pList;
    
    typedef struct mynode
    {
        void* next;
        void* prev;
        int data;
    } Node,*pNode;
    
    pList createlist()
    {
        pList root;
        pNode temp;
        int n;
        root = (pList)malloc(sizeof(List));         //malloc属于情况3
        root->head = NULL;
        root->tail = NULL;
        printf("input data number:");
        scanf("%d",&n);
        if(n&&NULL==root->head)
        {
            temp = (pNode)malloc(sizeof(Node));   //3
            printf("data1:");
            scanf("%d",&temp->data);
            temp->next = root;            //1
            temp->prev = root;            //1
            root->head = temp;           //1
            root->tail = temp;              //1
            n--;
        }
        for(int i=1; i<=n ; i++)
        {
            temp = (pNode)malloc(sizeof(Node));  //3
            printf("data%2d:",i);
            scanf("%d",&temp->data);
            temp->next = root;                   //1
            temp->prev = root->tail;          //2
            ((pNode)(root->tail))->next = temp; //5
            root->tail = temp;  //1
        }
        return root;
    }
    
    void printlist(pList root)
    {
        pNode temp = (pNode)root->head;   //3
        int i = 1;
        while(temp!=(pNode)root)                  //4
        {
            printf("data%2d:%d\n",i++,temp->data);
            temp = (pNode)temp->next;          //3
        }
    
        /*temp = (pNode)root->tail;
        while(temp!=(pNode)root)
        {
            printf("data%2d:%d\n",--i,temp->data);
            temp = (pNode)temp->prev;
        }*/
    }
    
    int main()
    {
        pList root;
        root = createlist();
        printlist(root);
    }
    


    展开全文
  • 题目实现反转单向链表和双向链表,要求:如果链表长度为N,时间复杂度为O(N),额外空间复杂度为O(1)参考答案图形表示单向链表单向反转请参考双向链表反转前:头节点的前驱是null,尾节点的后继是null。反转后:以前...

    题目

    实现反转单向链表和双向链表,要求:如果链表长度为N,时间复杂度为O(N),额外空间复杂度为O(1)

    参考答案

    图形表示

    单向链表

    单向反转请参考双向链表

    反转前:头节点的前驱是null,尾节点的后继是null。

    反转后:以前的头节点的后继是null,以前的尾节点的前驱是null

    java代码实现如下:

    {

    ;

    ;

    ;

    ( ) {

    .  ;

    }

    }{

    ([] ) {

    ();

    //构建一个双向链表1 2 3 4

    ();

    ();

    ();

    .  ;

    .  ;

    .  ;

    ..();

    ();

    ();

    ..();

    ();

    }

    //把自己的前驱变后继,把后继变前驱

    privatestaticDoubleNodereversalList(DoubleNodehead) {

    DoubleNodepre=null;

    DoubleNodenext;

    while(head!=null) {

    next=head.next;

    head.next=pre;

    head.pre=next;

    pre=head;

    head=next;

    }

    System.out.println();

    returnpre;

    }

    //遍历打印节点信息

    privatestaticvoidprint(DoubleNodehead) {

    while(head!=null) {

    System.out.print(head.value);

    //优化打印日格式

    System.out.print(" ");

    head=head.next;

    }

    }

    }

    关键字

    链表,单向,双向,反转

    展开全文
  • 二叉搜索树与双向链表题目描述解决思路(后续再改进)实现代码 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 链接:二叉搜索树...

    题目描述

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

    链接二叉搜索树与双向链表

    解决思路(写的有点拉跨后面再改)

    核心:怎么改变结点的前驱指向和后继指向
    在这里插入图片描述

    实现代码

    public class Solution {
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null) return null;
            ConvertChild(pRootOfTree); //中序遍历结束
            TreeNode head = pRootOfTree; //定义head指向头结点
            //从左向下遍历,直到head.next为空退出循环,此时的head就是链表的头结点
            while(head.left != null){
                head = head.left;
            }
            return head;
            
        }
        
        TreeNode prev = null;
        public void ConvertChild(TreeNode pCur){
            if(pCur == null) return ;
           
            ConvertChild(pCur.left);
            pCur.left = prev;
            //判断prev是否为空,下面if语句再第二轮遍历开始发挥作用
            if(prev != null){
                prev.right = pCur;
            }
            prev = pCur;
            ConvertChild(pCur.right);
        }
    }
    
    展开全文
  • 剑指offer 面试题27 二叉搜索树与双向链表 面试题: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点,只能调整树中结点指针的指向。 比如输入下图中左边的二叉搜索...
  • 问题 例子 思路 first为第一个结点,即...first可看作head,pre可看作cur,采用尾插法进行构造双向链表 方法1 $$ $$ 方法2 $$ $$ 代码 //方法1 递归 class Solution { private Node first; private N...
  • 题目实现反转单向链表和双向链表,要求:如果链表长度为N,时间复杂度为O(N),额外空间复杂度为O(1)参考答案图形表示单向链表单向反转请参考双向链表反转前:头节点的前驱是...
  • 面试题36:二叉搜索树与双向链表 题目描述: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 代码: class Solution { public: ...
  • 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有...
  • c++中的双向链表写法,主要实现(增删查改,链表逆置,构造函数,运算符重载,等) c++实现双向链表,类模板双向链表
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
  • 面试题27二叉搜索树与双向链表 思路:中序遍历一颗二叉搜索树的时候能够得到一个从小到大排序的有序序列。中序遍历二叉搜索树将其转换为双向链表。 其中left指针域作为双向链表的前驱指针,right指针域作为双向链表...
  • 链表面试题——C

    2017-09-02 12:07:47
    3、双向链表和单向链表相比,多了一个前驱指针,单向链表在删除结点时候要遍历链表,双向链表在删除不需要遍历。 一、判断两个链表是否相交:(假设两个链表都没有环)  1、判断第一个链表的每个节点是否在第...
  • 我们常用的链表基本都是单链表和双向链表,两种链表不同在于双向链表比单链表多了一个指向当前节点的前一个节点的指针域。 而复杂链表,相比单链表多了一个指向任意位置的随机域。复杂链表的结构如下: struct ...
  • 面试题27:二叉搜索树与双向链表 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 代码: package offer; /** *...
  • 微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
  • 解题思路:要将二叉搜索树转化为排序的循环双向链表,因为二叉树的性质我们知道左子树的所有节点都小于根节点,所有右子树的节点都大于根节点,我们可以递归的去求解双向链表,先分别求得做左子树的循环双向链表,再...
  • //如果左孩子不空,则递归转换左子树-->双向链表,并返回左子链表的最右端节点(最大值节点) if(pNode->m_pLeft) { pLeft = ConvertNode(pNode->m_pLeft,false); } //将当前节点与左子链表的最右端连接...
  • 面试题027】二叉搜索树与双向链表 题目: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调用书中结点的指向。 二叉树的结点定义如下: C++ Code ...
  •  * 面试题36:二叉搜索树与双向链表  * 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。  * 思路:1、将左子树构成双链表,并...
  • 面试题27. 二叉搜索树与双向链表 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路:由于是BST树,我们可以中序遍历树中的...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 二叉搜索树: 1.介绍:是一种特殊的二叉树,满足对树上的任意节点,左子树中的所有节点小于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,162
精华内容 464
关键字:

双向链表面试题