力扣二叉树题解含思路(C++实现)

1.求二叉树的最近公共祖先：

        原题链接：. - 力扣（LeetCode）

        假设这题的p，q分别为7和8，而它们的最近公共祖先肯定是为3。

这题我们大致的思路为保存p，q的绝对路径，接着通过存储的绝对路径去寻找第一个相同的节点假设公共节点。

        1.1：寻找7节点：

        

                1.2：8节点也是同样的方式进行：

        1.3：找到最近的公共节点

                

        代码：

class Solution {
public:
    bool Find(TreeNode* root,TreeNode* val,stack<TreeNode*>&st)
    {
        if(!root)
            return false;
        st.push(root);
        if(root==val)
            return true;

        if(Find(root->left,val,st))
            return true;
        if(Find(root->right,val,st))
            return true;

        //如果此时的节点的根，左子树，右子树都没有找到val，就说明val并不在这个节点，将这个节点pop掉。
        st.pop();
        return false;        
    }


    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        //1.使用两个栈用来保存p，q的绝对路径
        //2.接着pop较长的栈，保持两个栈相等
        //3.两个栈同时pop，最终得到相等的就是祖先
        stack<TreeNode*> st1;
        stack<TreeNode*> st2;
        Find(root,p,st1);
        Find(root,q,st2);

        while(st1.size()>st2.size())
            st1.pop();

        while(st2.size()>st1.size())
            st2.pop();
            
        while(st1.top()!=st2.top())
        {
            st1.pop();
            st2.pop();
        }
        return st1.top();
    }
};

2.二叉搜索树与双向链表

        原题链接：二叉搜索树与双向链表_牛客题霸_牛客网

        其实这题如果忽略题目要求就很简单，因为是标准的搜索二叉树，就通过中序遍历存入list题目就解决了，但小编应题目要求，空间复杂度为O(1)及在原树上操作。本题需要对递归有一定的理解才方便做。

        

        这里小编要提出一个穿越者思想，及把自己想象成一个可以穿越时间的人，而二叉树有left和right与根。将left想象成昨天，将right想象成明天。因为是搜索二叉树所以必然会走一个中序遍历，所以我们将在中序遍历上进行操作。

        条件1：我们知道昨天发生什么

        条件2：我们虽然不知道明天将发生什么，但我们穿越到明天后再回到今天就能知道明天发生什么。

        

        这里小编想多一嘴，为什么cur会回到6节点，因为我们采用的方式是递归，递归函数会进行压栈，当我们压入4节点的函数栈帧时候，6节点栈帧会保存在4节点下面，而当4节点函数结束时候，此时函数栈帧进行弹出销毁，6节点就是栈顶，所以此时cur的值就是6.而且因为递归的关系，就算指向改变了也不会影响中序遍历的顺序，因为已经将顺序全部压入栈中了。

                

        代码：

class Solution {
public:
bool TrainsTree(TreeNode*&prev,TreeNode*cur)
{
if(cur==nullptr)
return false;
TrainsTree(prev,cur->left);

cur->left=prev;
if(prev)
prev->right=cur;
prev=cur;
TrainsTree(prev, cur->right);
return true;
}

    TreeNode* Convert(TreeNode* pRootOfTree)
{
        TreeNode*prev=nullptr;
TrainsTree(prev, pRootOfTree);
TreeNode*head=pRootOfTree;
while (head&&head->left) {
head=head->left;
}
return  head;
    }
};

       代码看着很简单，就只是在改动指针之间的指向，但这就是递归的魅力，看着很简单，实际想出来很难。

3.从前序和中序遍历序列构建二叉树

        原题链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

        

        题目要求给定两个二叉树序列的数组，要求我们从两个序列中构建二叉树，那么我们先从画图思考如何构建。  

        代码：

class Solution {
public:
    TreeNode*_build(vector<int>& preorder, vector<int>& inorder,
                    int &pi,int ileft ,int iright )
    {
       if(ileft>iright)
            return nullptr;
       
        //使用前序遍历思想，进来就先确定根
        TreeNode *key=new TreeNode(preorder[pi]);
        
        //使用中序遍历思想，找到根，区分根的左子树与右子树
        int keyi=0;
        while(keyi<inorder.size())
        {
            if(inorder[keyi]==preorder[pi])
                break;
            keyi++;
        }

        pi++;

        //[ileft keyi-1] keyi [keyi+1 iright];
        key->left=_build(preorder,inorder,pi,ileft,keyi-1);
        key->right=_build(preorder,inorder,pi,keyi+1,iright);
        return key;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int pi=0, ileft=0 , iright=inorder.size()-1;
        return _build(preorder,inorder,pi,ileft,iright);
    }
};

        代码递归结束条件为ileft大于iright，就好比如我们想确定9是不是属于叶子节点，在递归9的左子树时，ileft=0，iright=-1，而在递归9的右子树时候会发现ileft=1，而iright=0。这显然不是一个有效的区间所以直接退出。

4.二叉树的前序遍历

        原题链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

        可能看到这有读者疑惑，这题不是很简单吗，为啥还需要拿出来讲。是的这题使用递归的思想就是很简单，但如果要求采用的是非递归的方式呢？应该怎么做

        

        

        假设我们需要前序遍历这颗子树应该怎么遍历呢？

        

        因为是前序遍历，所以我们在一开始遍历根的时候直接将值存入vector中，在将节点压入栈中。

        这里主要的核心是通过栈的先进先出的特性来模拟递归遍历的过程，当我们的cur指针只需要一直往左子树遍历。用栈去存储节点，当cur指向空的时候表明该根的左子树已经遍历完成，接着弹出栈顶节点，如果栈顶节点没有右节点就不用管，继续弹出下一个栈顶节点，而如果弹出的栈顶节点有右子树，那么我们就重新让cur指向我们弹出节点的右节点，接着继续遍历入栈循环。直到栈为空与cur指向为空，就表明该子树全部遍历完成了。

        代码：

    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> vv;
        stack<TreeNode*> st;
        TreeNode *cur=root;
        TreeNode *temp=nullptr;
        while(cur||!st.empty())
        {
            if(cur)
            {
                vv.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }
            else
            {
                temp= st.top();
                st.pop();
                cur=temp->right;  
            }
        }
        return vv;
    }

        

5.二叉树的后序遍历

        原题链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

        这题我们就以这颗二叉树为例，我们直到后序遍历为:左子树|右子树|根 而很显然在后序遍历的时候根节点会被访问两次,所以这题我们会两次访问根节点,而难点在于我们并不知道我们的右子树是否已经访问过了.

                

        代码:

 vector<int> postorderTraversal(TreeNode* root)
    {
        vector<int> vv;
        stack<TreeNode*> st;
        TreeNode *cur=root;
        TreeNode *temp=nullptr;
        TreeNode*prev=nullptr;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }

            //后序遍历二叉树会走两次根节点，
            //如果一个根的右节点没被访问，那么访问根的前一个节点为根的左子树
            //如果一个根的右子树被访问了，那么访问根的前一个节点为根的右子树
            temp=st.top();
            if(temp->right==nullptr || prev==temp->right)
            {
                vv.push_back(temp->val);
                st.pop();
                prev=temp;
                
            }else
            {
                cur=temp->right;
            }
        }
        return vv;
    }

                                

                                                                                                那么本片文章到这里就结束了,感谢各位观看,如果觉得对您有帮助,还请点点赞

原文地址：https://blog.csdn.net/2301_80894970/article/details/143661330

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！