leetcode刷题记录06（2023-04-19）【验证二叉搜索树(前序遍历) | 对称二叉树(不要闹，递归最简单) | 二叉树的层序遍历(队列/不断清空序列) | 二叉树的最大深度(队列)】

客官°小女子只卖身不卖艺 2024-03-23 14:34 10阅读 0赞

## 98. 验证二叉搜索树 ##

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

![在这里插入图片描述][5b80318311394648b88d4a2dd32d4f43.png]

输入：root = \[2,1,3\]  
输出：true

示例 2：

![在这里插入图片描述][abddc5f71d8a4da2b7790bbbea6c28ec.png]

输入：root = \[5,1,4,null,null,3,6\]  
输出：false  
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：  
树中节点数目范围在 \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\] 内  
 − 2 31 < = N o d e . v a l < = 2 31 − 1 -2^\{31\} <= Node.val <= 2^\{31\} - 1 −231<=Node.val<=231−1

最开始采用的方法是，通过递归遍历，来判断二叉搜索树是否满足局部排序，但是这种方法，不好考虑到全局是否可行，比如下面这棵树。

5
    	  /	  \
    	4		6
    		  /   \
    		3       7

这棵树就不是一颗符合条件的二叉搜索树，但是，我如果使用注释的方法，返回的结果就是true（因为他没有考虑到5和3的关系）。

代码如下：

class Solution {
        
        void digui(TreeNode* root, vector<int>& vec) {
        
            if (root->left != nullptr) {
        
                digui(root->left, vec);
            }
            vec.push_back(root->val);
            if (root->right != nullptr) {
        
                digui(root->right, vec);
            }
        }
    public:
        //bool isValidBST(TreeNode* root) {
        
        //    if (root == nullptr) {
        
        //        return true;
        //    }
    
        //    if (root->left != nullptr && root->val < root->left->val) {
        
        //        return false;
        //    }
        //    else {
        
        //        bool res = isValidBST(root->left);
        //        if (res == false)return false;
        //    }
    
        //    if (root->right != nullptr && root->val > root->right->val) {
        
        //        return false;
        //    }
        //    else {
        
        //        bool res = isValidBST(root->right);
        //        if (res == false)return false;
        //    }
    
        //    return true;
        //}
    
        bool isValidBST(TreeNode* root) {
        
            vector<int> vec;
            digui(root, vec);
            for (int i = 1; i < vec.size(); i++) {
        
                if (vec[i] <= vec[i - 1]) {
        
                    return false;
                }
            }
            return true;
        }
    };

## 101. 对称二叉树 ##

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

![在这里插入图片描述][20a6955161bc47b48707c7d0f040073c.png]

输入：root = \[1,2,2,3,4,4,3\]  
输出：true

示例 2：

![在这里插入图片描述][775fc4f2dcfc48948e000cd23295995d.png]

输入：root = \[1,2,2,null,3,null,3\]  
输出：false

提示：

树中节点数目在范围 \[1, 1000\] 内  
\-100 <= Node.val <= 100

第一种方法为 `递归` 的方法，思路就是，搞两个指针 `left` 和 `right` 然后分情况讨论：

*  如果他俩有一个空指针了，另外一个必须也是。是返回true，不是返回false。
 *  `left->val` 和 `right->val` 不相等，很显然返回false
 *  如果上面的都满足了，递归调用，判断 `left->left` 和 `right->right` 是否对称，同时判断 `left->right` 和 `right->left` 是否对称。

语言有些抽象，代码如下：

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 {
        
        bool testIsSame(TreeNode* left, TreeNode* right) {
        
            if (left == nullptr || right == nullptr) {
        
                if (left == right) {
        
                    return true;
                }
                else {
        
                    return false;
                }
            }
            if (left->val != right->val) {
        
                return false;
            }
            else {
        
                return testIsSame(left->left, right->right) && testIsSame(left->right, right->left);
            }
        }
    public:
        bool isSymmetric(TreeNode* root) {
        
            bool isSame = testIsSame(root->left, root->right);
            return isSame;
        }
    };

迭代的方法，如下，主要利用了 `stack` 这一数据结构。搞两个栈，宏观来讲，我们比较的就是 `root->left` 和 `root->right` 是否对称。因此，我们用两个栈来对他们分别进行存储。

这里遍历采用层次遍历的方法，前序遍历和中序遍历用迭代法有点绕，后续遍历更加绕，在此不在使用。遇到前、中、后序遍历的用递归法更加简单直接。

#include<stack>
    using namespace std;
    
    class Solution {
        
    public:
        bool isSymmetric(TreeNode* root) {
        
            TreeNode* left = root->left;
            TreeNode* right = root->right;
    
            stack<TreeNode*> stk_left;
            stack<TreeNode*> stk_right;
            if (left != nullptr)
                stk_left.push(left);
            if (right != nullptr)
                stk_right.push(right);
            
            while (!stk_left.empty() && !stk_right.empty())
            {
        
                left = stk_left.top();
                stk_left.pop();
    
    
                right = stk_right.top();
                stk_right.pop();
    
                if (left->val != right->val) {
        
                    return false;
                }
    
                if (left->left != nullptr && right->right != nullptr) {
        
                    stk_left.push(left->left);
                    stk_right.push(right->right);
                }
                else {
        
                    if (left->left != right->right) {
        
                        return false;
                    }
                }
    
                if (left->right != nullptr && right->left != nullptr) {
        
                    stk_left.push(left->right);
                    stk_right.push(right->left);
                }
                else {
        
                    if (left->right != right->left) {
        
                        return false;
                    }
                }
            }
            if (!stk_left.empty() || !stk_right.empty()) {
        
                return false;
            }
            else {
        
                return true;
            }
        }
    };

同时，递归方法相比于迭代方法性能并没有差很多，甚至更好一些（当然可能和我使用的层次遍历与测试用例分布的情况有关）。但至少可以说明，不会相差太多。

提交记录如下：

![在这里插入图片描述][33531439f537429884680b219e976d7f.png]

从执行时间和内存消耗两方面来看，递归方法看起来更有优势。

## 102. 二叉树的层序遍历 ##

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

![在这里插入图片描述][0ff24805241e483f8c5231bff36878d3.png]

输入：root = \[3,9,20,null,null,15,7\]  
输出：\[\[3\],\[9,20\],\[15,7\]\]

示例 2：  
输入：root = \[1\]  
输出：\[\[1\]\]

示例 3：  
输入：root = \[\]  
输出：\[\]

提示：  
树中节点数目在范围 \[0, 2000\] 内  
 − 1000 < = N o d e . v a l < = 1000 -1000 <= Node.val <= 1000 −1000<=Node.val<=1000

这道题目运用队列进行层次遍历。

主要思想是对深度进行一个记录。

后面利用深度信息对节点进行填充。

#include<vector>
    #include<queue>
    using namespace std;
    
    // 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:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            // 如果为 0 层二叉树，直接返回空 vector
            if (root == nullptr) {
        
                return {
        };
            }
            vector<int> deep;       // 用来记录每个节点的深度
            int index = -1;         // 用来记录当前节点的序号（从 0 开始
            deep.push_back(0);  // 第一个节点记录为 0
    
            queue<TreeNode*> que;   // 存储节点的队列
    
            que.push(root);     // 放入根节点
    
            TreeNode* cur = nullptr; // 当前访问到的节点
    
            vector<int> vec;         // 从前往后存储节点
            while (!que.empty()) {
        
                index++;
                cur = que.front();
                vec.push_back(cur->val); // 记录节点值
                que.pop();
                if (cur->left != nullptr) {
        
                    que.push(cur->left);
                    deep.push_back(deep[index] + 1); // 记录层数
                }
                if (cur->right != nullptr) {
        
                    que.push(cur->right);
                    deep.push_back(deep[index] + 1); // 记录层数
                }            
            }
    
            // 数组 1 维长度应该为树的深度 deep[index] + 1
            vector<vector<int>> result(deep[index] + 1, vector<int>());
            for (int i = 0; i < vec.size(); i++) {
              // 再次遍历所有节点
                result[deep[i]].push_back(vec[i]);  // 按照深度进行数组的填充
            }
            return result;
        }
    };

## 104. 二叉树的最大深度 ##

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：  
给定二叉树 \[3,9,20,null,null,15,7\]，

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

主要思路为每次输出每一层的节点，然后加入下一层的节点，很巧妙。

代码如下：

#include<queue>
    using namespace std;
    // 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) {
        
            if (root == nullptr) {
        
                return 0;
            }
            queue<TreeNode*> que;
            que.push(root);
            int deep = 0;
            TreeNode* cur = nullptr;
            while (!que.empty())
            {
        
                deep++;
                int n = que.size();
                for (int i = 0; i < n; i++) {
        
                    cur = que.front();
                    que.pop();
                    if (cur->left != nullptr) {
        
                        que.push(cur->left);
                    }
                    if (cur->right != nullptr) {
        
                        que.push(cur->right);
                    }
                }
            }
            return deep;
        }
    };

利用这道题的思路可以对上面题目 `102` 题很好地进行改进了。

[5b80318311394648b88d4a2dd32d4f43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9062551f4d1f47ae869706533659b536.png
[abddc5f71d8a4da2b7790bbbea6c28ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/784f7e9437a84bbb93605d1767160d64.png
[20a6955161bc47b48707c7d0f040073c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/5bc39c4e56f047c89dae12d15968bb8c.png
[775fc4f2dcfc48948e000cd23295995d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/341cd35f8a5d41d8b1e6aac81d5c36d5.png
[33531439f537429884680b219e976d7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6e85643e8cc446dd8dfaa0810cb5304f.png
[0ff24805241e483f8c5231bff36878d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/f010d86b16d344c3bb6532d753c1a98b.png