二叉树经典题题解(超全题目)(力扣)

这篇具有很好参考价值的文章主要介绍了二叉树经典题题解(超全题目)(力扣)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  •   力扣 二叉树经典,刷题,算法,c++,leetcode

 ✨欢迎来到脑子不好的小菜鸟的文章✨

      🎈创作不易,麻烦点点赞哦🎈

          所属专栏:刷题  

          我的主页:脑子不好的小菜鸟

          文章特点:关键点和步骤讲解放在

          代码相应位置

目录

144. 二叉树的前序遍历

145. 二叉树的后序遍历

 94. 二叉树的中序遍历

 102. 二叉树的层序遍历

 107. 二叉树的层序遍历 II

 199. 二叉树的右视图

 637. 二叉树的层平均值

429. N 叉树的层序遍历

515. 在每个树行中找最大值

116. 填充每个节点的下一个右侧节点指针

 117. 填充每个节点的下一个右侧节点指针 II

104. 二叉树的最大深度

111. 二叉树的最小深度

226. 翻转二叉树

589. N 叉树的前序遍历

590. N 叉树的后序遍历

101. 对称二叉树

144. 二叉树的前序遍历

题目链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//中左右

/*法一:递归法*/

class Solution {
public:
    void traversal(TreeNode* root,vector<int>& vec/*类似于数组*/)
    {
        if(root==NULL)
        return;

        vec.push_back/**/(root->val);
        traversal(root->left,vec);
        traversal(root->right,vec);
    }
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int>result;
        traversal(root,result);
        return result;
    }
};

/*法二:迭代法
因为递归是用栈实现的,所以迭代法也用栈实现,
因为弹出的顺序是    中左右,所以栈的位置(左边封闭):右左中
先把根节点放进栈,再放入  右  节点,再放进左节点(因为栈是先进后出),再一一弹出*/

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int>result;
        if(root==NULL)
        return result;

        stack<TreeNode*>st;

        st.push(root);
        while(!st.empty())
        {
            TreeNode* cur=st.top();
            st.pop();

            if(cur==NULL)
            continue;

            result.push_back(cur->val);

            st.push(cur->right);/******/
            st.push(cur->left);
        }

        return result;
    }
};
/*法三:统一迭代法(注释是中序遍历的)*/

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int>result;

        if(root==NULL)
        return result;

        stack<TreeNode*>st;
        TreeNode* cur=root;
        st.push(cur);
        
        //中左右---->放的时候应该为右左中
        while(!st.empty())
        {
            cur=st.top();
            if(cur!=NULL)//加入节点入栈,记住中间节点是遍历节点,而不是操作节点,所以要标记(在后面加NULL)
            {
                st.pop();//因为先放进去右节点

                if(cur->right!=NULL) st.push(cur->right);/*!!!!!!!!注意要不为空才可以放入,不然else部分会运行错误!!!!!!*/

                if(cur->left!=NULL) st.push(cur->left);
                
                st.push(cur);
                st.push(NULL);/**/
            }
            else
            {
                st.pop();//把NULL弹出

                cur=st.top();
                st.pop();

                result.push_back(cur->val);
            }
        }
        return result;
    }
};

145. 二叉树的后序遍历

题目链接:https://leetcode.cn/problems/binary-tree-postorder-traversal/



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//左右中

/*法一:迭代法*/

// class Solution {
// public:
//     void traversal(TreeNode* root,vector<int>& vec/*类似于数组*/)
//     {
//         if(root==NULL)
//         return;

//         traversal(root->left,vec);
//         traversal(root->right,vec);
//         vec.push_back/**/(root->val);
//     }
    
//     vector<int> postorderTraversal(TreeNode* root) 
//     {
//         vector<int>result;
//         traversal(root,result);
//         return result;
//     }
// };

/*法二:迭代法
因为递归是用栈实现的,所以迭代法也用栈实现,与前序遍历的迭代法类似
左右中,所以栈的样子(左边闭合):中右左---->把前序遍历的左右顺序换一下,再整个数组调转
*/

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int>result;
        if(root==NULL)
        return result;

        stack<TreeNode*>st;

        st.push(root);
        while(!st.empty())
        {
            TreeNode* cur=st.top();
            st.pop();

            if(cur==NULL)
            continue;

            result.push_back(cur->val);

            st.push(cur->left);
            st.push(cur->right);/******/
        }
        reverse(result.begin(),result.end());
        return result;
    }
};
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int>result;

        if(root==NULL)
        return result;

        stack<TreeNode*>st;
        TreeNode* cur=root;
        st.push(cur);
        
        //左右中---->放的时候应该为中右左
        while(!st.empty())
        {
            cur=st.top();
            if(cur!=NULL)//加入节点入栈,记住中间节点是遍历节点,而不是操作节点,所以要标记(在后面加NULL)
            {
                st.pop();//因为先放进去右节点

                st.push(cur);
                st.push(NULL);/**/

                if(cur->right!=NULL) st.push(cur->right);/*!!!!!!!!注意要不为空才可以放入,不然else部分会运行错误!!!!!!*/

                if(cur->left!=NULL) st.push(cur->left);
                
            }
            else
            {
                st.pop();//把NULL弹出

                cur=st.top();
                st.pop();

                result.push_back(cur->val);
            }
        }
        return result;
    }
};
/*法三:统一迭代法(注释是中序遍历的)*/

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int>result;

        if(root==NULL)
        return result;

        stack<TreeNode*>st;
        TreeNode* cur=root;
        st.push(cur);
        
        //左右中---->放的时候应该为中右左
        while(!st.empty())
        {
            cur=st.top();
            if(cur!=NULL)//加入节点入栈,记住中间节点是遍历节点,而不是操作节点,所以要标记(在后面加NULL)
            {
                st.pop();//因为先放进去右节点

                st.push(cur);
                st.push(NULL);/**/

                if(cur->right!=NULL) st.push(cur->right);/*!!!!!!!!注意要不为空才可以放入,不然else部分会运行错误!!!!!!*/

                if(cur->left!=NULL) st.push(cur->left);
                
            }
            else
            {
                st.pop();//把NULL弹出

                cur=st.top();
                st.pop();

                result.push_back(cur->val);
            }
        }
        return result;
    }
};



 94. 二叉树的中序遍历

题目链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/



//左中右

/*法一:递归法*/
class Solution {
public:
    void Traversal(TreeNode* cur,vector<int>& result)
    {
        if(cur==NULL)
        return;

        Traversal(cur->left,result);
        result.push_back(cur->val);
        Traversal(cur->right,result);
    }

    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int>result;
        Traversal(root,result);
        return result;
    }
};

/*法二:迭代法
与前序遍历后序遍历不同,注意 遍历节点 和 处理节点 的区别
解题方法:需要一个指针去遍历二叉树,
若遍历的节点为空,则将栈顶元素加入答案,并弹出栈顶元素;
若不为空,则将该元素加入栈中,再将指针指向该元素的左节点
当栈和节点都为空,遍历结束
*/

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int>result;

        if(root==NULL)
        return result;

        stack<TreeNode*>st;
        TreeNode* cur=root;
        
        while(!st.empty()||cur!=NULL)//注意是||
        {
            if(cur!=NULL)
            {
                st.push(cur);
                cur=cur->left;
            }
            else
            {
                cur=st.top();
                /*注意是cur*/
                st.pop();
                result.push_back(cur->val);
                cur=cur->right;
            }
        }
        return result;
    }
};
但是发现三种迭代法不统一,不统一的原因是:前后序遍历是处理节点与遍历节点相同,但是中序不相同
/*法三:统一迭代法*/

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int>result;

        if(root==NULL)
        return result;

        stack<TreeNode*>st;
        TreeNode* cur=root;
        st.push(cur);
        
        //左中右---->放的时候应该为右中左
        while(!st.empty())
        {
            cur=st.top();
            if(cur!=NULL)//加入节点入栈,记住中间节点是遍历节点,而不是操作节点,所以要标记(在后面加NULL)
            {
                st.pop();//因为先放进去右节点

                if(cur->right!=NULL) st.push(cur->right);/*!!!!!!!!注意要不为空才可以放入,不然else部分会运行错误!!!!!!*/

                st.push(cur);
                st.push(NULL);/**/

                if(cur->left!=NULL) st.push(cur->left);
            }
            else
            {
                st.pop();//把NULL弹出

                cur=st.top();
                st.pop();

                result.push_back(cur->val);
            }
        }
        return result;
    }
};

 102. 二叉树的层序遍历

题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal/



/*模板!!!!!!!!!!!!!!
层序遍历靠二叉树是不可以实现的,所以需要一个队列+size来存储
*/

/*
注意在C++中:
一维数组的定义:vector<数组 元素 的数据类型>
二维数组的定义:vector<一维数组>
vector是push_back
queue是push,front
*/

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>>result;
        int size;
        TreeNode* cur=root;
        queue<TreeNode*>que;
        if(cur!=NULL)
            que.push(cur);//注意是push,不是push_back

        while(!que.empty())
        {
            size=que.size();
            vector<int>vec;
            while(size--)
            {
                TreeNode* p=que.front();//注意是front,不是top
                vec.push_back(p->val);//注意是push_back
                que.pop();

                if(p->left!=NULL) que.push(p->left);
                if(p->right!=NULL) que.push(p->right);

            }
            result.push_back(vec);
        }
        return result;
    }
};

 107. 二叉树的层序遍历 II

题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/



//二叉树的层序遍历的答案数组翻转就好

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        vector<vector<int>>result;
        int size;
        TreeNode* cur=root;
        queue<TreeNode*>que;
        if(cur!=NULL)
            que.push(cur);//注意是push,不是push_back

        while(!que.empty())
        {
            size=que.size();
            vector<int>vec;
            while(size--)
            {
                TreeNode* p=que.front();//注意是front,不是top
                vec.push_back(p->val);//注意是push_back
                que.pop();

                if(p->left!=NULL) que.push(p->left);
                if(p->right!=NULL) que.push(p->right);

            }
            result.push_back(vec);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

 199. 二叉树的右视图


题目链接:https://leetcode.cn/problems/binary-tree-right-side-view/



//一直往右走(想得太简单了)----->正确思路:看是不是该层最右边的元素---->同样设置size,size=1的时候就是最右边的

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        vector<int>result;
        int size;
        TreeNode* cur=root;
        queue<TreeNode*>que;

        if(cur!=NULL)
            que.push(cur);//注意是push,不是push_back

        while(!que.empty())
        {
            size=que.size();

            while(size)
            {
                cur=que.front();/**/

                if(size==1)
                result.push_back(cur->val);

                que.pop();
                if(cur->left!=NULL) que.push(cur->left);
                if(cur->right!=NULL) que.push(cur->right);
                size--;
            }
            //cur=cur->right;(错误写法)
        }
        return result;
    }
};

 637. 二叉树的层平均值


题目链接:https://leetcode.cn/problems/average-of-levels-in-binary-tree/



//

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) 
    {
        long long sum=0;
        double average=0.0;
        vector<double>result;
        int size,size1;
        queue<TreeNode*>que;//注意<>内的类型

        TreeNode*cur=root;
        if(cur!=NULL)
        que.push(cur);

        while(!que.empty())
        {
            sum=0;
            size=que.size();
            size1=size;

            while(size1--)
            {
                cur=que.front();
                sum+=cur->val;

                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            average=sum*1.0/size;
            result.push_back(average);
        }
        return result;
    }
};

429. N 叉树的层序遍历


https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
 


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>>result;
        queue<Node*>que;
        Node* cur=root;
        int size;

        if(cur!=NULL)
        que.push(cur);

        while(!que.empty())
        {
            vector<int>vec;
            size=que.size();

            while(size--)
            {
                cur=que.front();
                vec.push_back(cur->val);

                que.pop();

                for(int i=0;i<cur->children.size();i++)
                {
                    if(cur->children[i]) que.push(cur->children[i]);
                }
            }
            result.push_back(vec);
        }   
        return result;
    }
};

515. 在每个树行中找最大值

https://leetcode.cn/problems/find-largest-value-in-each-tree-row/



//

class Solution {
public:
    vector<int> largestValues(TreeNode* root) 
    {
        vector<int>result;
        int max=INT_MIN;
        int size;
        queue<TreeNode*>que;
        TreeNode* cur=root;

        if(cur==NULL)
        return result;
        que.push(cur);

        while(!que.empty())
        {
            size=que.size();
            max=INT_MIN;/*每次都要更新*/
            while(size--)
            {
                cur=que.front();
                que.pop();
                if(cur!=NULL&&cur->val>max)
                max=cur->val;

                if(cur->left)   que.push(cur->left);
                if(cur->right)  que.push(cur->right);

            }
            result.push_back(max);
        }
        
        return result;
    }
};

116. 填充每个节点的下一个右侧节点指针


https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) 
    {
        Node* cur=root;
        queue<Node*>que;
        int size;

        if(cur==NULL)
        return root;

        que.push(cur);

        while(!que.empty())
        {
            size=que.size();
            Node* Precur;
            Node* cur;
            for(int i=0;i<size;i++)
            {
                if(i==0)
                {
                    Precur=que.front();
                    que.pop();
                    cur=Precur;/*!!!!!!!!!!!!!111*/
                }
                else
                {
                    cur=que.front();
                    que.pop();
                    Precur->next=cur;
                    Precur=Precur->next;
                }
                if(cur->left)   que.push(cur->left);
                if(cur->right)  que.push(cur->right);
            }
            Precur->next=NULL;
        }
        return root;
    }
};

 117. 填充每个节点的下一个右侧节点指针 II

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) 
    {
        queue<Node*>que;
        if(root==NULL)
        return root;

        que.push(root);
        int size;

        while(!que.empty())
        {
            size=que.size();
            Node* precur;
            Node* cur;
            for(int i=0;i<size;i++)
            {
                if(i==0)
                {
                    precur=que.front();
                    que.pop();
                    cur=precur;
                }
                else
                {
                    cur=que.front();
                    que.pop();
                    precur->next=cur;
                    precur=precur->next;
                }
                if(cur->left)   que.push(cur->left);
                if(cur->right)  que.push(cur->right);
            }
            precur->next=NULL;
        }
        return root;
    }
};

104. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/


/*使用迭代法的话,使用层序遍历是最为合适的,因为最大的深度就是二叉树的层数,和层序遍历的方式极其吻合。

在二叉树中,一层一层的来遍历二叉树,记录一下遍历的层数就是二叉树的深度*/


class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        int deepth=0;
        queue<TreeNode*>que;
        int size;
        if(root==NULL)
        return 0;

        TreeNode* cur=root;
        que.push(cur);

        while(!que.empty())
        {
            size=que.size();
            deepth++;
            while (size--)
            {
                cur = que.front();
                que.pop();

                if(cur->left)   que.push(cur->left);
                if(cur->right)  que.push(cur->right);
            }
        }
        return deepth;
    }
};

111. 二叉树的最小深度


https://leetcode.cn/problems/minimum-depth-of-binary-tree/



//最先左右孩子都为空的层数为最小深度

class Solution {
public:
    int minDepth(TreeNode* root) 
    {
        int deepth=0;
        queue<TreeNode*>que;
        TreeNode* cur=root;
        int size;

        if(root==NULL)
        return 0;

        que.push(cur);

        while(!que.empty())
        {
            size = que.size();
            deepth++;
            while(size--)
            {
                cur=que.front();
                que.pop();

                if(cur->left)   que.push(cur->left);
                if(cur->right)  que.push(cur->right);

                /*注意是放在while(size--)里面*/
                if(cur->left==NULL&&cur->right==NULL)
                    return deepth;
            }
        }
        
        return deepth;
    }
};

226. 翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/
 


//每个节点的左右都翻转一下就好
//该题可用前中后序,前序和后序是最好的,而中序要绕弯子,在表面上看是操作了两次左子树
//也可用层序遍历

/*法一:层序遍历*/
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==NULL)
        return root;

        queue<TreeNode*>que;
        TreeNode* cur=root;
        que.push(cur);
        int size;

        while(!que.empty())
        {
            size=que.size();

            while(size--)
            {
                cur=que.front();
                que.pop();
                swap(cur->left,cur->right);

                if(cur->left)   que.push(cur->left);
                if(cur->right)  que.push(cur->right);
                
                
            }
        }
        return root;

    }
};

// /*法二:前序遍历(后续遍历只是把swap的操作换一下位置)*/
class Solution {
public:
    TreeNode* Swap(TreeNode* cur)
    {
        if(cur==NULL)
        return cur;

        swap(cur->left,cur->right);
        Swap(cur->left);
        Swap(cur->right);

        return cur;

    }
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==NULL)
        return root;
        Swap(root);
        return root;

    }
};


/*法三:中序遍历*/
class Solution {
public:
    TreeNode* Swap(TreeNode* cur)
    {
        if(cur==NULL)
        return cur;

        Swap(cur->left);
        swap(cur->left,cur->right);
        Swap(cur->left);/*left!!!!!!!*/

        return cur;

    }
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==NULL)
        return root;
        Swap(root);
        return root;

    }
};

589. N 叉树的前序遍历

https://leetcode.cn/problems/n-ary-tree-preorder-traversal/
 


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    Node* traversal(Node* cur,vector<int>& result)
    {
        if(cur==NULL)
        return cur;

        result.push_back(cur->val);
        int size=cur->children.size();
        for(int i=0;i<size;i++)
        traversal(cur->children[i],result);

        return cur;
    }

    vector<int> preorder(Node* root) 
    {
        int size;
        vector<int>result;
        traversal(root,result);
        return result;

    }
};

590. N 叉树的后序遍历


https://leetcode.cn/problems/n-ary-tree-postorder-traversal/
 


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    Node* traversal(Node* cur,vector<int>& result)
    {
        if(cur==NULL)
        return cur;

        int size=cur->children.size();
        for(int i=0;i<size;i++)
        traversal(cur->children[i],result);

        result.push_back(cur->val);

        return cur;
    }

    vector<int> postorder(Node* root) 
    {
        int size;
        vector<int>result;
        traversal(root,result);
        return result;

    }
};

101. 对称二叉树


https://leetcode.cn/problems/symmetric-tree/文章来源地址https://www.toymoban.com/news/detail-850326.html



/*法一:递归法*/

/*两个关键点:
1.遍历顺序:后序,因为要把两个孩子的信息传给父节点才知道左右父节点的孩子一不一样---->要把两个孩子的信息传给父节点的题目都是用后序遍历
2.解题关键:要知道看是否对称是看右子树是不是左子树翻转过来的,左子树里侧 = 右子树里侧    左子树外侧 = 右子树外侧*/

class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right)
    {
        /*注意是else if*/
        if(left==NULL&&right!=NULL) return false;
        else if(left!=NULL&&right==NULL) return false;
        else if(left==NULL&&right==NULL) return true;
        else if(left->val!=right->val)  return false;
        else
        {
            bool inside = compare(left->right,right->left);//内侧
            bool outside = compare(left->left,right->right);//外侧
            bool result=inside&&outside;
            return result;
        }
    }
    bool isSymmetric(TreeNode* root) 
    {
        if(root==NULL)  return true;
        return compare(root->left,root->right);
    }
};

/*迭代法(注意不是层序遍历)---->用 栈和队列 都可以,类似*/

//队列

class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(root==NULL)  return true;
        queue<TreeNode*>que;

        TreeNode* cur = root;
        que.push(cur->left);
        que.push(cur->right);

        while(!que.empty())
        {
            TreeNode* leftNode = que.front();
            que.pop();
            TreeNode* rightNode = que.front();
            que.pop();

            if(leftNode==NULL&&rightNode==NULL) continue;//return true;
            else if(leftNode!=NULL&&rightNode==NULL)   return false;
            else if(leftNode==NULL&&rightNode!=NULL)    return false;
            else if(leftNode->val!=rightNode->val)  return false;
            else
            {
                que.push(leftNode->left);//左子树的左孩子
                que.push(rightNode->right);//右子树的右孩子
                que.push(leftNode->right);//左子树的右孩子
                que.push(rightNode->left);//右子树的左孩子
            }
        }
        
        return true;
   }
};

//栈:与队列出容器的顺序不同而已

class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(root==NULL)  return true;
        stack<TreeNode*>st;

        TreeNode* cur = root;
        st.push(cur->left);
        st.push(cur->right);

        while(!st.empty())
        {
            TreeNode* rightNode = st.top();//注意顺序
            st.pop();
            TreeNode* leftNode = st.top();
            st.pop();

            if(leftNode==NULL&&rightNode==NULL) continue;//return true;
            else if(leftNode!=NULL&&rightNode==NULL)   return false;
            else if(leftNode==NULL&&rightNode!=NULL)    return false;
            else if(leftNode->val!=rightNode->val)  return false;
            else
            {
                st.push(leftNode->left);//左子树的左孩子
                st.push(rightNode->right);//右子树的右孩子
                st.push(leftNode->right);//左子树的右孩子
                st.push(rightNode->left);//右子树的左孩子
            }
        }
        
        return true;
   }
};

到了这里,关于二叉树经典题题解(超全题目)(力扣)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++力扣题目101--对称二叉树

    力扣题目链接(opens new window) 给定一个二叉树,检查它是否是镜像对称的。   首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了 其实我们要比较

    2024年01月25日
    浏览(37)
  • C++力扣题目654--最大二叉树

    给定一个不重复的整数数组  nums  。  最大二叉树  可以用下面的算法从  nums  递归地构建: 创建一个根节点,其值为  nums  中的最大值。 递归地在最大值  左边  的  子数组前缀上  构建左子树。 递归地在最大值  右边  的  子数组后缀上  构建右子树。 返回  nums  构

    2024年01月20日
    浏览(38)
  • C++力扣题目617--合并二叉树

    给你两棵二叉树:  root1  和  root2  。 想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则

    2024年01月20日
    浏览(41)
  • C++力扣题目104--二叉树的最大深度

    给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 返回它的最大深度 3 。 看完本篇可以一起做了如下两道题目: 104.二叉树的最大深度(opens n

    2024年01月16日
    浏览(63)
  • 力扣第236题——二叉树的最近公共祖先 (C语言题解)

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

    2024年01月20日
    浏览(40)
  • C++力扣题目--94,144,145二叉树非递归(迭代)遍历

    为什么可以用迭代法(非递归的方式)来实现二叉树的前后中序遍历呢? 我们在栈与队列:匹配问题都是栈的强项 (opens new window)中提到了, 递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 ,然后递归返回的时候,从栈顶弹出上

    2024年02月02日
    浏览(36)
  • 【LeetCode】(力扣) c/c++刷题-145. 二叉树的后序遍历

    来源:力扣(LeetCode) 链接: 力扣  

    2024年02月01日
    浏览(61)
  • 数据结构之二叉树与堆以及力扣刷题函数扩展

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.树 2.1概念  2.2树的相关概念 3.堆 3.1堆的概念 3.2小堆函数实现 4.力扣刷

    2024年02月04日
    浏览(40)
  • 【刷题笔记8.11】LeetCode题目:二叉树中序遍历、前序遍历、后序遍历

    (一)题目描述 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 (二)分析 二叉树中序遍历,遍历顺序:左节点 -》 根节点 -》 右节点 ( 注意:二叉树的前、中、后序遍历就是以根为基准,前序遍历根在最前面,中序遍历根在中间,后序遍历根在最后面 ) (三)

    2024年02月13日
    浏览(36)
  • 【算法题解】34. 二叉树的最小深度

    这是一道 简单 题 https://leetcode.cn/problems/minimum-depth-of-binary-tree/ 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明 :叶子节点是指没有子节点的节点。 示例 1: 示例 2: 提示: 树中节点数的范围在 [ 0 , 1 0 5 ] [0, 10^5] [

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包