Leetcode初级算法——树

#pragma once
#include<algorithm>
#include<queue>
//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:
    int maxDepth(TreeNode* root) {

        /*by myself(深度优先,递归实现)
        if (root == nullptr) {          //遍历到空结点返回
            return 0;
        }

        return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;      //比较每个递归层root的左子树和右子数深度，返回值为 其中的最大深度再加1（因为root本身也是一层，当前递归层最大深度即 max(maxDepth(root->left), maxDepth(root->right)) + 1）

        */


        //(广度优先,使用了队列)
        if (root == nullptr) {        //如果为空树返回0，否则在if (t->left != nullptr)判断时会非法引用
            return 0;
        }

        std::queue<TreeNode*>que;     //队列的作用是存放当前层所有的结点
        int level = 0;                //记录二叉树最大深度(层数)
        
        que.push(root);               //首先将第一层的root节点入队
        while (!que.empty()) {                 //如果队列为空，表示遍历到最深一层，由于最深一层都没有子结点，所以当进入下一层查找时最深一层作为父结点会被出队
            int father_nodes = que.size();     //father_nodes表示这一层结点的个数（也是下一层的父节点的个数）

            while (father_nodes) {             //遍历这一层父结点，查找是否存在子节点，存在就入队，每个父结点查找完毕后将其出队，因此队列里都是下一层的子结点（每次遍历队列中的上层父节点，入队其子结点后删除父结点，队列中的这层子结点将作为下一层的父结点继续遍历查找。直到遍历到最深一层，最深一层的结点没有子结点，所以遍历后没有可入队的子结点，并且删除队列里的这层父结点，因此队列最后为空）
                TreeNode* t = que.front();

                if (t->left != nullptr) {
                    que.push(t->left);
                }
                if (t->right != nullptr) {
                    que.push(t->right);
                }
                que.pop();
                father_nodes--;    //遍历查找后删除一个父结点，father_nodes--
            }

            level++;               //内层while循环结束，表示一层遍历完毕，因此level++
        }

        return level;              //返回最后得到的level，即最大深度

    }
};

验证二叉搜索树

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

#pragma 
#include<iostream>
#include<stack>
//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:
    bool helper(TreeNode* root, long long min, long long max);

    bool isValidBST(TreeNode* root) {

        /* (错误理解) 只考虑到子结点和上一层父结点直间的大小关系，而没有考虑到全部（例如，不仅右子结点应大于其父节点的值，而是整个右子树的所有结点(包括其左子结点)都应该大于其父结点的值）
         * if (root->left != nullptr && root->right != nullptr) {
         *    if (root->val <= root->left->val || root->val >= root->right->val) {
         *        return false;
         *    }
         *
         *    if (!isValidBST(root->left)) {
         *        return false;
         *    }      
         *    if (!isValidBST(root->right)) {
         *        return false;
         *    }
         * }
         * return true;
         */
        

        /*(递归)
        return helper(root, LONG_MIN, LONG_MAX);

        */


        //(中序遍历,迭代，利用栈)
        std::stack<TreeNode*>stk;         //使用栈来模拟中序遍历的过程

        long long min = LONG_MIN;         //定义一个最小值（如果满足二叉搜索树再结合中序遍历特点，可知中序遍历后的所以结点是从小到大排列的。所以只要按照中序遍历对所有结点进行比较，如果满足从小到大的次序则是二叉搜索树）
                                          
        while (!stk.empty() || root != nullptr) {     //初始时，栈是空的，root!=nullptr(非空树)；中序遍历过程中，栈不是空的，root==nullptr或者root!=nullptr(即右结点可能是空也可能不是)；遍历结束时，栈是空的，root==nullptr（所有应该为||而不是&&，否则进入不了循环，中间遍历过程也可能突然退出）
            while (root != nullptr) {     //只要left存在就一直找left，直到nullptr
                stk.push(root);           //左要保留在栈中
                root = root->left;
            }

            root = stk.top();             //当root==nullptr(即left_r->left==nulltr),弹出left_r，root=left_r
            stk.pop();
            if (root->val <= min) {       //此时的root(left_r)即 中，将 中 与min比较，如果 中>=min，则说明不是二叉搜索树（不管前序、中序、后序遍历，所有结点都会有作为 中，比如前序遍历第一次遍历到该结点就是 中，中序遍历第二次遍历到该结点就是 中，后续遍历第三次遍历到该结点就是 中。所有所有结点都会成为中别遍历到，三种遍历只是说最终所有结点作为 中 被遍历到的顺序不同而已）
                return false;
            }
            min = root->val;              //min被设置为被遍历到的结点值，接着与下一个 中 比较
            root = root->right;           //找完了左，中，找右(以右作为新的子树root，继续不断找左)  
        }

        return true;                      //如果完整中序遍历完，说明该树就是二叉搜索树
    }
};

bool Solution::helper(TreeNode* root, long long min, long long max) {    //自己设计一个递归函数，增加每个结点值范围的参数(min,max)
    if (root == nullptr) {        //遍历到空结点，返回true
        return true;
    }

    if (root->val <= min || root->val >= max) {    //该结点不在范围内，即不满足二叉搜索树，返回false
        return false;
    }

    return helper(root->left, min, root->val) && helper(root->right, root->val, max);     //对左右子树进行递归，只有在都返回true时才满足二叉搜索树的条件（这里对左子树root的范围为(min, root->val)，对左子树root的范围为(root->val, max)。min和max在动态变化，即被覆盖，最终的目的就是要满足，对于左子树而言:左子树上的所有结点都应该小于这个左子树root，虽然存在树里面的子树，不管是外层树还是内层子树，只要该结点在其树上，既要小于外层树root,也要小于内存子树的root）


}

对称二叉树

#pragma once
#include<deque>
#include<queue>
#include<stack>
#include<vector>

//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:

    bool is_hui_wen(std::deque<TreeNode*> DQ_t);  //验证双端队列DQ_t中存储的结点是否构成回文（DQ_t中存储二叉树当前层的结点）
    bool is_hui_wen(std::vector<TreeNode*> vec);  //验证双端队列DQ_t中存储的结点是否构成回文（vec中存储二叉树当前层的结点的值）
    bool compare(TreeNode* t1, TreeNode* t2);     //比较对称位置t1,t2结点是否都存在，如果存在是否值相同
    bool check(TreeNode* t1, TreeNode* t2);       //官方代码简化版

    bool isSymmetric(TreeNode* root) {
        /*by myself(层序遍历，回文判断，有点暴力味)
        
        std::deque<TreeNode*>DQ;
        std::deque<TreeNode*>DQ_t;
        TreeNode* t = new TreeNode(-1);           //假设所有结点值都>0，在这里t代指一个空结点，起到占位作用（埋了个内存泄露的伏笔）
        

        DQ.push_back(root);
        DQ_t.push_back(root);

        while (!DQ.empty()) {       //中序遍历
            if (!is_hui_wen(DQ_t)) {              //如果当前层的结点按从左到右顺序不构成回文，则直接返回false
                return false;
            }
            DQ_t.clear();                         //清空双端队列DQ_t，即清空上一层结点，准备存入当前层结点

            int level_nodes = DQ.size();          //双端队列DQ_t中存储着上一层结点，寻找当前层结点是根据上一层结点进行
            while (level_nodes) {                 //根据上一层记录的结点，寻找下一层结点
                root = DQ.front();

                if (root->left != nullptr) {      //以上一层结点为root，如果存在左右结点，则插入到DQ和DQ_t中(每查找完DQ中存储的当前root结点，如果存在其左右则插入，插入完删除该root，继续查找DQ中下一个root)
                    DQ.push_back(root->left);    
                    DQ_t.push_back(root->left);
                }
                else {                           
                    DQ_t.push_back(t);            //如果root不存在left或者right，对于DQ是不插入的，但是对于DQ_t需要插入一个t
                }
                if (root->right != nullptr) {
                    DQ.push_back(root->right);
                    DQ_t.push_back(root->right);
                }
                else {
                    DQ_t.push_back(t);
                }

                DQ.pop_front();
                level_nodes--;       //每查找完上一层一个结点，level_nodes--，当level_nodes==0，表示上一层结点查找遍历完毕
            }
        }

        return true;
        */


        /*by myself(层序遍历，回文判断，简单优化：用queue和vector代替deque)
        
        std::queue<TreeNode*>Q;
        std::vector<TreeNode*>vec;


        Q.push(root);
        vec.push_back(root);

        while (!Q.empty()) {        //中序遍历
            if (!is_hui_wen(vec)) {               //如果当前层的结点按从左到右顺序不构成回文，则直接返回false
                return false;
            }
            vec.clear();                          //清空vec，即清空上一层结点，准备存入当前层结点

            int level_nodes = Q.size();           //队列Q中存储着上一层结点，寻找当前层结点是根据上一层结点进行
            while (level_nodes) {                 //根据上一层记录的结点，寻找下一层结点
                root = Q.front();

                if (root->left != nullptr) {      //以上一层结点为root，如果存在左右结点，则插入到Q和vec中(每查找完DQ中存储的当前root结点，如果存在其左右则插入，插入完删除该root，继续查找Q中下一个root)
                    Q.push(root->left);
                    vec.push_back(root->left);
                }
                else {
                    vec.push_back(nullptr);       //如果root不存在left或者right，对于Q是不插入的，但是对于vec需要插入一个nullptr（nullptr起到占位作用）
                }
                if (root->right != nullptr) {
                    Q.push(root->right);
                    vec.push_back(root->right);
                }
                else {
                    vec.push_back(nullptr);
                }

                Q.pop();
                level_nodes--;                    //每查找完上一层一个结点，level_nodes--，当level_nodes==0，表示上一层结点查找遍历完毕
            }
        }

        return true;

        */


        /*by myself(递归)
        
        return compare(root->left, root->right);

        */


        /*(递归，代码排放简明，逻辑性更强)
        
        return check(root->left, root->right);

        */

        
        /*by myself(迭代,栈实现)
        
        std::stack<TreeNode*>stk;   
        stk.push(root);
        stk.push(root);
        TreeNode* t1 =root->left;
        TreeNode* t2 = root->right;

        while (!stk.empty()) {    

            if (t1 == nullptr && t2 != nullptr || t1 != nullptr && t2 == nullptr) {        //1.在新的一轮开始时要判断 "t1父结点的right，t2父结点的left"作为新的root的两个结点(新一轮初始时判断)
                return false;
            }
            while (t1 != nullptr && t2 != nullptr) {      //从当前树，不断向下查找比较left和right结点，无非三种情况：(1)t1,t2都为nullptr,返回flase; (2)t1,t2只有一个为nullptr,返回false; (3)t1,t2都不为nullptr,值相对返回true,否则返回false;
                if (t1->val != t2->val) {                 //能正常从循环中出来，说明t1==nullptr，t2==nullptr,否则都会返回false。
                    return false;
                }
                stk.push(t1);
                stk.push(t2);
                t1 = t1->left;              //不断查找判断 左和右 结点
                t2 = t2->right;
                if (t1 == nullptr && t2 != nullptr || t1 != nullptr && t2 == nullptr) {   //2.在向下查找比较 左和右结点 时要判断(过程中判断)
                    return false;
                }
            }

            t2 = stk.top()->left;        //当t1==nullptr，t2==nullptr，此应该继续查找 "t1父结点的right，t2父结点的left "，并且t1，t2各自的父结点作为root的俩颗子树，继续查找比较 左和右 结点
            stk.pop();                   //注：由于是栈的缘故，开始是t1、t2入栈，此时应该以t2、t1顺序接收出栈值(stk.top()即他们的父结点)
            t1 = stk.top()->right;
            stk.pop();
            
        }

        return true;

        */

          
        //(迭代，队列实现)
        std::queue<TreeNode*>Q;        

        Q.push(root->left);
        Q.push(root->right);
        while (!Q.empty()) {               //结合广度优先遍历理解，只不过这里是同时处理俩组(左右，右左)，但也是一层一层处理
            TreeNode* t1 = Q.front();      //和广度优先遍历类似，当t1,t2作为父结点的时候应移除队列，并且在此时进行比较
            Q.pop();
            TreeNode* t2 = Q.front();
            Q.pop();

            if (t1 == nullptr && t2 == nullptr) {
                continue;
            }
            if (t1 == nullptr || t2 == nullptr || t1->val != t2->val) {
                return false;
            }

            Q.push(t1->left);            //对于两个位置对称的父结点t1,t2来说：t1->left和t2->right；t1->right和t2->left是两组位置对称的子结点，将他们加入队列
            Q.push(t2->right);

            Q.push(t1->right);            
            Q.push(t2->left);
        }

        return true;
    }
};


bool Solution::is_hui_wen(std::deque<TreeNode*> DQ_t) {    //判断是否为构成回文
    while (!DQ_t.empty()) {
        TreeNode* first = DQ_t.front();
        TreeNode* last = DQ_t.back();
        if (first->val != last->val) {
            return false;
        }

        if (DQ_t.size()>1) {
            DQ_t.pop_front();
            DQ_t.pop_back();
        }
        else {
            DQ_t.pop_front();
        }
    }
    
    return true;
}

bool Solution::is_hui_wen(std::vector<TreeNode*>vec) {    //判断是否为构成回文
    auto first = vec.begin();
    auto last = vec.end()-1;

    while (first < last) {
        if ((*first != nullptr && *last != nullptr) && (*first)->val != (*last)->val) {            //first、last是有效的结点则比较值，不等则不构成回文，返回false
            return false;
        }
        if ((*first == nullptr && *last != nullptr) || (*first != nullptr && *last == nullptr)) {  //first、last其中一个为有效结点，一个为无效结点，则肯定不构成回文，返回false
            return false;                                                                          //满足条件情况：first、last都为无效结点 或者 都为有效结点且值相等
        }

        first++;      
        last--;
    }

    return true;
}


bool Solution::compare(TreeNode* t1, TreeNode* t2) {     //t1,t2两个结点是对称结点(位置对称)
    if (t1 != nullptr && t2 != nullptr) {                //如果是对称二叉树，最起码每个结点都有一个与之位置对称的结点
        if (t1->val == t2->val) {                        //每个结点不仅要有位置上对称的结点，而且结点值要相等。在满足这样的条件下才有必要继续递归比较下去
            if (!compare(t1->left, t2->right)) {    //可知t1和t2是两个位置对称结点(从root开始推就可知，t1处于root的左，t2处于root的右)，所以接下来要比较t1,t2这俩个结点的子结点也必须对称，所以t1->left对应的是t2->right，t1->right对应的是t2->left。(一个左一个右才呈对称位置)
                return false;                       //如果compare函数返回false则直接向上一层返回false
            }
            if (!compare(t1->right, t2->left)) {
                return false;
            }
        }
        else {                                           //如果对称位置上两个结点值不等，返回false
            return false;
        }
        
    }

    if ((t1 == nullptr && t2 != nullptr) || (t1 != nullptr && t2 == nullptr)) {   //如果一个结点连对称位置上都不存在相应对称结点，肯定不满足对称二叉树，直接返回false
        return false;
    }

    return true;       //上面俩个if如果都不满足，说明t1,t2都为nullptr,说明这一递归层的对应位置都是空结点，直接返回上一层，所以返回true
}

bool Solution::check(TreeNode* t1, TreeNode* t2) {      //官方代码简化版,无非三种情况: (1)t1,t2都为nullptr,返回flase; (2)t1,t2只有一个为nullptr,返回false; (3)t1,t2都不为nullptr,值相对返回true,否则返回false;
                                              //我是按(3)(2)(1)顺序写，(3)(2)为俩个if,剩下自然是(1)，放在return。官方an(1)(2)(3)，先写明(1)(2)俩代码量最少的，剩下情况自然就是(3)，(3)代码量最多，放在return，省去了冗余的判断，因为(1)(2)判断完，剩下肯定是(3)这种情况不用再次判断
    if (t1 == nullptr && t2 == nullptr) {     
        return true;
    }
    if (t1 == nullptr || t2 == nullptr) {     //根据上面判断知道，到这里说明t1,t2不可能都为nullptr，所以判断t1,t2是否只有一个为nullptr时，只需要判断t1==nullptr或t2==nullptr就行，满足就返回flase
        return false;
    }

    return (t1->val == t2->val) && check(t1->left, t2->right) && check(t1->right, t2->left);  //因为经过了(1)(2)判断这里默认就是(3)成立，即t1,t2都不为空。利用了&&的特点，先把(t1->val == t2->val)放前面，满足才会判断后来俩个函数，即继续递归，否则直接跳过后面俩个函数返回flase，正好和(3)对上。
}

二叉树的层序遍历