【二叉树进阶题目】236. 二叉树的最近公共祖先,JZ36 二叉搜索树与双向链表

2023-12-13 08:08:00

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例
在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身

解题思路及实现

思路一

在这里插入图片描述

class Solution {
public:
    //中序遍历的变形---->Find
    bool InOrder(TreeNode* root,TreeNode* node)
    {
        if(root == nullptr)
            return false;

        if(root == node)
            return true;

         return InOrder(root->left,node) || InOrder(root->right,node);
         
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if(root == nullptr)
            return nullptr;

        //p或q是根
        if(root == p || root == q)
            return root;
        
        //找p,找q, 注意p,q一定在树中
        bool pInLeft=InOrder(root->left,p);
        bool pInRight=!pInLeft;
        bool qInLeft=InOrder(root->left,q);
        bool qInRight=!qInLeft;

        //判断
        if((pInLeft && qInRight) || (pInRight && qInLeft))
            return root;
        else if(pInLeft && qInLeft)
            return lowestCommonAncestor(root->left,p,q);
        else
            return lowestCommonAncestor(root->right,p,q);
    }
};

在这里插入图片描述
虽然代码没问题,但是运行效率太差了。分析一下上面是什么原因导致的。
在这里插入图片描述

如果这颗树是一个二叉搜索树,我们就不需要去子树寻找了。
又或者这是一颗三叉树。

在这里插入图片描述

思路二

在这里插入图片描述

class Solution {
public:
    //DFS<----->前序遍历
    //我们这里是回溯,回溯也是DFS,特点是往回走做一些事情
    //关于回溯,DFS,前序遍历不要深究到底是什么有什么区别,其实都是递归
    bool GetPath(TreeNode* root,TreeNode* node,stack<TreeNode*>& st)
    {
        if(root == nullptr)
            return false;

        st.push(root);
        
        if(root == node)
            return true;
        

        if(GetPath(root->left,node,st))
            return true;

        if(GetPath(root->right,node,st))
            return true;

        st.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {


        if(root == nullptr)
            return nullptr;

        stack<TreeNode*> pst;
        stack<TreeNode*> qst;

        GetPath(root,p,pst);
        GetPath(root,q,qst);

        while(pst.size() != qst.size())
        {
            if(pst.size() > qst.size())
                pst.pop();
            else
                qst.pop();
        }

        while(pst.top() != qst.top())
        {
            pst.pop();
            qst.pop();
        }
        return pst.top();
    }
};

JZ36 二叉搜索树与双向链表

JZ36 二叉搜索树与双向链表这是一道牛客上面的题。

描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示
在这里插入图片描述
数据范围:输入二叉树的节点数0≤n≤1000,二叉树中每个节点的值 0≤val≤1000
要求:空间复杂度O(1)(即在原树上操作),时间复杂度 O(n)

注意:
1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构
4.你不用输出双向链表,程序会根据你的返回值自动打印输出

解题思路及实现

在这里插入图片描述

class Solution {
public:
	//prev必须加个引用,不然等到递归返回上一层的时候
	//明明prev=cur了,但是返回到上一层prev还是nullptr
	void ConvertLink(TreeNode* cur,TreeNode*& prev)
	{	
		if(cur == nullptr)
			return;

		ConvertLink(cur->left, prev);
		cur->left=prev;

		if(prev)
			prev->right=cur;

		prev=cur;

		ConvertLink(cur->right, prev);

	}

    TreeNode* Convert(TreeNode* pRootOfTree) {

		if(pRootOfTree == nullptr)
			return nullptr;
			
        TreeNode* prev=nullptr;

		ConvertLink(pRootOfTree,prev);

		//找链表头,链接之后,pRootOfTree还在
		while(pRootOfTree->left)
			pRootOfTree=pRootOfTree->left;
		
		return pRootOfTree;

    }
};

文章来源:https://blog.csdn.net/fight_p/article/details/134570126
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。