Leetcode 101：对称二叉树

题目描述

给定一个二叉树，检查它是否是镜像对称的。

解题思路

既然它是镜像的话，那么就是左右对称，这个我们可以使用一个递归来解决。我们令A等于这个树，B也等于这个树，假设A树和B树都只有一个结点（空结点也看做是一个结点）其实也就是两个树中至少一个树为NULL的时候，结果只会存在三种情况：
1.A的该结点为NULL，B的该结点也为NULL，即都是空结点，那么这两个树相等，自然是镜像，返回true；
2.A的该结点为NULL，B的该结点不为NULL（或者A的该结点不是NULL，B的该结点为NULL），那么不是镜像，返回false；
3.A和B均有值，但不相等，自然不是镜像，返回false。
我们把这个结点看做是其父结点的一个子树，然后逐层向上去扩展。
判断的时候是由上向下，只要两个结点值相等就继续递归。

代码实现

 bool isSym(TreeNode* root1, TreeNode* root2)
{
    if (root1 == nullptr && root2 == nullptr)
        return true;
    if (root1 == nullptr || root2 == nullptr)
        return false;
    if (root1->val != root2->val)
        return false;
    return isSym(root1->left, root2->right) && isSym(root1->right, root2->left);
}
bool isSymmetric(TreeNode* root) {
    return isSym(root, root);
}

时间复杂度&空间复杂度

Leetcode 102：二叉树的层序遍历

题目描述

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

解题思路

这其实就是二叉树的BFS，但是和之前又有一点不同，那就是保存的结果不是一个vector，而是一个vector类型的vector数组，数组里面有多个vector，每个vector里面的元素是这一层的值。所以关键在于如何存储呢？那这个就可以借鉴之前做过的二叉树的右视角这个题，我们储存一个size，代表这一层有多少个元素，然后执行一个for循环，在这个for循环里面把元素push到一个tmp数组中，for循环完成后，把tmppush到result即可。

但是不知道为什么，那个for循环如果我用while循环的话，就会超时，需要研究一下。

代码实现

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr)
        return result;
    queue<TreeNode*>q;
    TreeNode* tt;
    q.push(root);
    while (!q.empty())
    {
        int size = q.size();
        vector<int>tmp;
        for(int i=0;i<size;i++)
        {
            tt = q.front();
            tmp.push_back(tt->val);
            q.pop();
            if (tt->left)
                q.push(tt->left);
            if (tt->right)
                q.push(tt->right);
        }
        result.push_back(tmp);
    }
    return result;
}

执行用时和内存消耗

Leetcode 104：二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

示例

给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度为3。

题目解析：递归法

如果一棵树只有一个结点，那么深度为1.如果根节点只有左子树而没有右子树，那么深度就是左子树深度+1；同理，对于右子树也是如此。如果既有左子树，也有右子树，那么该树的深度就是左右子树深度的最大值+1。所以可以利用递归的方式实现该题目。

代码实现：递归法

int maxDepth(TreeNode* root) {
        int Heightl,Heightr,MaxH;
        if(root)
        {
            Heightl=maxDepth(root->left);
            Heightr=maxDepth(root->right);
            MaxH=(Heightl>Heightr)?Heightl:Heightr;
            return MaxH+1;
        }
        else
        {
            return 0;
        }
    }

题目解析：广度优先

借鉴层序遍历的方法，只不过使用了deque，不具体说思路了，比较简单。

代码实现：广度优先

int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        deque<TreeNode* > q;
        q.push_back(root);
        int deep=0;
        while(!q.empty())
        {
            ++deep;
            int len=q.size();
            for(int i=1;i<=len;i++)
            {
                TreeNode *tt=q.front();
                q.pop_front();
                if(tt->left)
                    q.push_back(tt->left);
                if(tt->right)
                    q.push_back(tt->right);
            }
        }
        return deep;
    }

时间复杂度&空间复杂度

递归法：

广度优先：

可以看出，广度优先算法提升了速度，减小了内存消耗。