(第27天)【leetcode题解】101、对称二叉树 100、相同的树 572、另一颗树的子树

101、对称二叉树

题目描述

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

思路

题目分析：

• 检查二叉树是否对称，就是要检查根节点root的左右子树是否对称
• 怎样检查root的左右子树是否对称呢？当root的左子树所有左子节点的值等于右子树所有右子节点的值 且 左子树所有右子节点的值等于右子树所有左子节点的值`时，这个二叉树时对称二叉树

递归法：

1. 返回值:bool
2. 参数。left:root的左子树，right:root的右子树
3. 终止条件：考虑左右子树的当前节点都为空的情况、考虑左右子树当前节点不相等的情况
4. 递归逻辑：先向左右子树的外侧递归，对外侧节点进行比较；在向左右子树的内侧递归，对内侧节点进行比较。
5. 递归函数做了什么？：根据传入的参数，采用类似于后序遍历的方式比较了左右子树的外侧节点值和内侧节点值。

使用队列实现迭代：

1. 若根节点非空，使用队列，往队列中按左右顺序加入左右子树的根节点。
2. 进入循环，每次取出两个节点比较，若值不同返回false。(要对节点为NULL的情况做额外处理)
3. 为了保证比较的节点符合判断二叉树是否对称的题目要求，在循环体的最后按照左子树的左节点、右子树的右节点、左子树的右节点、右子树的左节点的顺序把节点放入队列中。

使用栈实现迭代：

1. 核心思路：要判断二叉树是否对称，需要分别比较左右子树外侧节点和内侧节点。那么，把需要比较的元素按顺序放进容器中，每次取出一对进行比较就可以实现效果。

代码

递归法：

class Solution {
public:
    //递归函数
    //参数：left左子树、right右子树
    bool helper(TreeNode* left, TreeNode* right) {
        //终止条件
        //先考虑左右子树为空的情况
        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;

        //递归逻辑
        bool outside = helper(left -> left, right -> right);//左子树:左  右子树:右(比较外侧节点)
        bool inside = helper(left -> right, right -> left);//左子树:右  右子树:左(比较内侧节点)
        bool issame = outside && inside;//左子树:中 右子树:中
        return issame;//外侧节点和内侧节点都相等时返回true
    }

    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return helper(root -> left, root -> right);//传入左右子树
    }
};

使用队列实现迭代：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root -> left);
        que.push(root -> right);
        while (!que.empty()) {
            TreeNode* LeftNode = que.front(); que.pop();
            TreeNode* RightNode = que.front(); que.pop();

            if (!LeftNode && !RightNode) continue;//若比较的两个节点都为空，说明这时是对称的
            //若两节点有一个为空，或两节点的值不同，则不对称，直接返回flase
            if (!LeftNode || !RightNode || (LeftNode -> val != RightNode -> val)) return false;

            //按顺序把节点加入队列中
            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;
        st.push(root -> left);
        st.push(root -> right);
        while (!st.empty()) {
            TreeNode* leftNode = st.top(); st.pop();
            TreeNode* rightNode = st.top(); st.pop();

            if (!leftNode && !rightNode) continue;
            if (!leftNode || !rightNode || (leftNode -> val != rightNode -> val)) return false;

            st.push(leftNode -> left);
            st.push(rightNode -> right);
            st.push(leftNode -> right);
            st.push(rightNode -> left);
        }
        return true;
    }
};

100、相同的树

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路

递归法：

1. 返回值：bool
2. 参数：p、q，代表子树和子树的节点
3. 终止条件：p、q为空时对称；p、q有一个不为空时不对称；p、q都不为空但值不同时不对称。
4. 递归逻辑：先比较p的所有左子节点和q的所有左子节点、再比较p的所有右子节点和q的所有右子节点。

迭代法：

1. 把需要比较的元素成对相邻的放入容器中，然后依次成对取出进行比较，若两个值不相同则表示两棵树不一样。

代码

递归法：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;//都为空，相同
        else if (p == NULL || q == NULL || (p -> val != q -> val)) return false;

        return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right);
    }
};

迭代法：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;
        queue<TreeNode*> que;
        que.push(p);
        que.push(q);
        while (!que.empty()) {
            TreeNode* qNode = que.front(); que.pop();
            TreeNode* pNode = que.front(); que.pop();

            if (qNode == NULL && pNode == NULL) continue;
            if (qNode == NULL || pNode == NULL || qNode -> val != pNode -> val) return false;

            que.push(qNode -> left);
            que.push(pNode -> left);
            que.push(qNode -> right);
            que.push(pNode -> right);
        }
        return true;
    }
};

572、另一颗树的子树

题目描述

• 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

• 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

思路

• 题目分析：

要检验一棵树是否是另一颗树的子树的三种可能：

1. 两棵树相同：根节点都为空 或 两棵树相同
2. 这棵树是另一颗树的左树的子树
3. 这棵树是另一颗树的右树的子树

1. 判断两棵树相同

根节点都为空，相同；根节点只有一个为空，不同。
比较当前的两个节点值
向左递归、向右递归

2. 判断是否是大树左树的子树

主函数向左递归，每个递归里都判断一次当前子树是否和待检测树相同

3. 判断是否是大树右树的子树

主函数向右递归，每个递归里都判断一次当前子树是否和待检测树相同

代码

class Solution {
public:
    bool isSameTree(TreeNode* root, TreeNode* subRoot) {
        if (root == NULL && subRoot == NULL) return true;//两棵树都为空时，相同
        else if (root == NULL || subRoot == NULL ) return false;//只有一个为空是，不同
        return (root->val == subRoot->val) //先比较两个节点的值
        && isSameTree(root->left, subRoot->left) //向左递归,比较左子树
        && isSameTree(root->right, subRoot->right);//向右递归，比较右子树
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == NULL && subRoot == NULL) return true;//两棵树都为空
        if (root == NULL && subRoot != NULL) return false;//大树为空，小树不为空
        return isSameTree(root, subRoot) //两树相同
        || isSubtree(root->left, subRoot)//判断subRoot是否是左树的子树
        || isSubtree(root->right, subRoot);//判断subRoot是否是右数的子树
    }
};

总结

• 在对节点进行比较时，要处理好节点为空的情况

因为在这一类型题中，比较节点值是通过node -> val进行的，若没有处理节点为空的情况，则在处理数据时会报错。
因此，对于节点为空的情况，需要单独处理。