二叉树应用_树中两个节点的最低公共祖先

青旅半醒 2022-05-22 04:05 181阅读 0赞

题目：给定树中的两个节点，找出这两个节点的最低公共祖先。

情况1：当给定的树为二叉搜索树时。  
分析：由于二叉搜索树是排序过的，位于左子树的节点都小于根节点，位于右子树的节点都大于根节点。如果要查找的两个节点比根节点大的话，则最低公共祖先在右子树中；如果要查找的两个节点比根节点小的话，则最低公共祖先在左子树中。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    
    TreeNode*findlastparent(TreeNode*root,TreeNode*pnode1,TreeNode*pnode2)
    {
        if(root->val>pnode1->val && root->val>pnode2->val)
            return findlastparent(root->left,pnode1,pnode2);
        else if(root->val<pnode1->val && root->val<pnode2->val)
            return findlastparent(root->right,pnode1,pnode2);
        else
            return root;
    }

情况二：树为普通的二叉树  
分析：找到分别包含要查找结点的路径，并将路径存在一个向量中，在根据这两个向量找到第一个公共节点即为公共的祖先。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    
    bool findpath(TreeNode*root,TreeNode*pnode,vector<TreeNode*>&path)
    {
        if(root==NULL)
            return false;
        if(root==pnode)
        {
            path.push_back(root);
            return true;
        }
        path.push_back(root);
        if(findpath(root->left,pnode,path))
            return true;
        if(findpath(root->right,pnode,path))
            return true;
        path.pop_back();
        return false;
    }
    TreeNode* getcommandnode(vector<TreeNode*>&path1,vector<TreeNode*>&path2)
    {
        vector<TreeNode*>::iterator it1=path1.begin();
        vector<TreeNode*>::iterator it2=path2.begin();
        TreeNode*plast=NULL;
        while(it1!=path1.end()&&it2!=path2.end())
        {
            if(*it1=*it2)
                plast=*it1;
            ++it1;
            ++it2;
        }
        return plast;
    }
    
    TreeNode*findlastparent(TreeNode*root,TreeNode*pnode1,TreeNode*pnode2)
    {
        if(root==NULL||pnode1==NULL||pnode2==NULL)
            return NULL;
    
        vector<TreeNode*>path1,path2;
        findpath(root,pnode1,path1);
        findpath(root,pnode2,path2);
    
        return getcommandnode(path1,path2);
    }

情况三：当连二叉树都不是只是一个普通的树时。  
分析：其实这种情况和情况二类似，只是在寻找路径时遍历孩子，不只是左右孩子。

struct TreeNode
    {
        int                    m_nValue;
        std::vector<TreeNode *>    m_vChildren;
    };
    
    //只是需要更改findpath函数
    bool findpath(TreeNode*root,TreeNode*pnode,vector<TreeNode*>&path)
    {
        if(root==NULL)
            return false;
        if(root==pnode)
        {
            path.push_back(root);
            return true;
        }
        path.push_back(root);
        bool found=false;
        vector<TreeNode *>::iterator it=root->m_vChildren.begin();
        while(it!=m_vChildren.end()&&!found)
        {
            found=findpath(*it,pnode,path);
            ++it;
        }
        if(!found)
            path.pop_back();
        return found;
    }