【leetcode100-038/039/040/041】【二叉树】翻转/对称/直径/层序遍历

发布时间:2024年01月18日

今天看题目真的太简单了,干脆一起写了。

【二叉树翻转】

给你一棵二叉树的根节点?root?,翻转这棵二叉树,并返回其根节点。

思路:

先交换左右子节点,再递归处理左右子树(或者反过来也行)。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return root;
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

【镜像二叉树】

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

思路:

还是递归的方式去做。首先左右孩子自身要对称,也就是val相等,然后递归地去判断左右子树是否镜像。

class Solution {
public:
    bool check(TreeNode* root1,TreeNode* root2){
        if(root1==nullptr&&root2==nullptr)return true;
        if(!(root1&&root2))return false;
        if(root1->val!=root2->val)return false;
        return check(root1->left,root2->right)&&check(root1->right,root2->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr)return true;
        //左右子树是否互为镜像
        return check(root->left,root->right);
    }
};

【二叉树直径】

思路:

本题有个比较关键的地方,就是路径不一定过根节点,这就意味着要对每个节点都做直径计算,而且不一定层次更高的节点它的结果就会优于层次低的节点,所以答案并不是从下往上传递的,我们需要弄一个全局变量来记录它,保证随便在哪一层递归里面都可以顺利地访问它。

具体操作方面呢,对一个节点来说,我们计算以它为最高节点的最长路径长度(它作为过程节点的路径,会在更高层次被计算,这样限定可以保证不做重复计算,而且,不这样限定也没法算了。。),显然,我们分别往左右子树走出最长的路径,然后加起来,就可以得到答案。左右子树最长路径怎么来呢?经典求树高。用人话说就是,左右子树取高的然后+1,至于左右子树树高怎么来,递归!

class Solution {
public:
    int height(TreeNode* root, int& curMax) {
        if (root == nullptr)
            return 0;
        int L = height(root->left, curMax);
        int R = height(root->right, curMax);
        curMax = max(curMax, L + R);
        return max(L, R) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int curMax = 0;
        height(root, curMax);
        return curMax;
    }
};

【层序遍历】

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

思路:

这个题。。我愿称之为STL练习题而不是算法练习题,因为它的重点是要你返回的格式。。。是一个vector<vector<int>>,而不是正常层序遍历那完整的一串。

这太好解决了啊,遍历每一层的时候构造一个vector存东西,这层遍历完了以后把它整个存进ans就好了。你问怎么判断哪些节点是同一层的?计数。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> ans;
        if (root != nullptr)
            q.push(root);
        while (!q.empty()) {
            TreeNode* cur = nullptr;
            int cnt = q.size();
            vector<int> layer;
            while (cnt) {
                cur = q.front();
                q.pop();
                layer.push_back(cur->val);
                if (cur->left)
                    q.push(cur->left);
                if (cur->right)
                    q.push(cur->right);
                cnt--;
            }
            ans.push_back(layer);
        }
        return ans;
    }
};

文章来源:https://blog.csdn.net/weixin_63059689/article/details/135679440
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。