Day18 226翻转二叉树 101对称二叉树 100相同的树 572另一棵树的子树

226 翻转二叉树

递归前序遍历和后序遍历：

class Solution {
public:
    void swap(TreeNode*&a,TreeNode*&b)
    {
        TreeNode*tmp = a;
        a = b;
        b = tmp;
    }
    void reverseTree(TreeNode* cur)
    {
        if(cur==nullptr) return;
        swap(cur->left,cur->right);
        reverseTree(cur->left);
        reverseTree(cur->right);
        //后序遍历把这里顺序调换一下就行
    }
    TreeNode* invertTree(TreeNode* root) {
        reverseTree(root);
        return root;
    }
};

????????递归中序遍历，这里需要有点区别了，如果按照正常的中序，那有些孩子可能在左边翻转完，到右面又翻转了一次，类似于今年一年级擦黑板，明年二年级擦黑板的情况。所以要做修改：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};

? ? ? ? ?另外本题还可以进行迭代法，其实也类似，迭代中序的话可能要有点变化：

//迭代前序
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode*cur=st.top();
            st.pop();
            swap(cur->left, cur->right);
            if(cur->right) st.push(cur->right);
            if(cur->left) st.push(cur->left);
        }
        return root;
    }
};

//迭代中序
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); 
                st.pop();
                swap(cur->left,cur->right);   // 中
                cur = cur->left;               // 右
            }
        }
        return root;
    }
};

? ? ? ? 但是如果用统一迭代法就不会存在这个问题了，因为是用栈来遍历而不是指针来遍历。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if(root != nullptr)
            st.push(root);
        while(!st.empty())
        {
            TreeNode*node = st.top();
            if(node)
            {
                st.pop();
                if(node->right) st.push(node->right);

                st.push(node);
                st.push(nullptr);

                if(node->left) st.push(node->left);
            }
            else
            {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);
            }
        }
        return root;
    }
};

? ? ? ? 同时也可以进行层序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != nullptr) que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            while(size--)
            {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left,node->right);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

? ? ? ? 总而言之，这道题比较简单，可以尝试多种遍历方式举一反三，注意中序的重复问题。

101 对称二叉树

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

? ? ? ? 首先由于上一题的影响，我想到的是将这个二叉树翻转，之后对比翻转前后是否相等，来判断这个二叉树是不是对称二叉树，但是出现了一些问题，总会有些特殊的情况最后两组的数据是相同的但是并不是对称二叉树，不管怎么遍历都是差一点，错误代码附上吧：

class Solution {
public:
void reverseTree(TreeNode* &cur) //翻转二叉树
    {
        if(cur==nullptr) return;
        swap(cur->left,cur->right);
        reverseTree(cur->left);
        reverseTree(cur->right);
    }
    void traversal(TreeNode* cur, vector<int>& vec) //遍历二叉树
    {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
         vec.push_back(cur->val);
        traversal(cur->right, vec); // 右

    }
    bool isSymmetric(TreeNode* root) {
        vector<int> v1;
        traversal(root, v1);
        vector<int> v2;
        reverseTree(root);
        traversal(root, v2);
        for(int i = 0; i < v1.size(); i++)
        {
            if(v1[i] != v2[i]) return false;
        }
        return true;
    }
};

? ? ? ? 此时，我想到了不如用层序遍历，为了避免出现上面方法的错误情况，即使是空的地方我也要给创造一个结点顶上去，但是不能创造太多，否则内存会爆，于是定义的结点为INT_MIN，在下一层创建节点是，如果没有左右孩子并且val为INT_MIN，则不会再创建，这样比较省内存，代码如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        
        if(root) q.push(root);

        while(!q.empty()){
            int size = q.size();
            vector<int> vec;

            for(int i = 0; i<size; i++){
                TreeNode* node = q.front();
                q.pop();
                vec.push_back(node->val);
                if(node->left) q.push(node->left); 
                else if(node->val != INT_MIN) q.push(new TreeNode(INT_MIN)); 
                if(node->right) q.push(node->right);
                else if(node->val != INT_MIN) q.push(new TreeNode(INT_MIN));
            }
            
            vector<int> vec1;
            vec1.assign(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());

            if(vec != vec1) return false;
        }

        return true;
    }
};

????????再后面就是代码随想录的后序递归遍历方法了：比较的是根节点的两颗子树，所以在递归遍历的过程中，也是要同时遍历两棵树。为什么要后序，要遍历两颗子树而且要比较内侧和外侧结点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

? ? ? ? 我们来列写递归三部曲

1.确定递归函数的参数和返回值

我们要比较的是根节点的两颗子树是否是相互翻转的，进而判断对称，所以参数为两棵子树，返回值为bool类型。

bool?compare(TreeNode*?left,?TreeNode*?right)

2.确定终止条件：

首先要把两个节点为空的情况列写出，左空右不空，左不空右空，都是不对称return false；如果左右都为空，说明对称，返回true；后面如果节点数值不同就返回false。

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; // 注意这里我没有使用else

?3.确定单层递归的逻辑

比较内外侧是否对称，如果其中有一侧不对称，就返回false；

bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
return isSame;

最后整体代码如下：

class Solution {
public:
    bool compare(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;

        //可以用这个代替下面的几行：else return compare(left->left, right->right) && compare(left->right, right->left);
        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(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;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            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;
    }
};

?100 相同的树

给你两棵二叉树的根节点?p?和?q?，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

?和上面非常类似，把compare函数稍作修改即可，让后面的对比内外变成对比的一致即可。

class Solution {
public:
    bool isSameTree(TreeNode* left, TreeNode* right) {
        if(left==nullptr&&right!=nullptr) return false;
        else if(left!=nullptr&&right==nullptr) return false;
        else if(left==nullptr&&right==nullptr) return true;
        else if(left->val!=right->val) return false;

        bool comleft = isSameTree(left->left, right->left);
        bool comright = isSameTree(left->right, right->right);
        bool Issame = comleft && comright;
        return Issame;
    }
};

572 另一棵树的子树

?

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

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

? ? ? ? ?这道题可以利用上面的判断两棵树是否相同来简化，后面的issubtree中，参数题里已经给了，终止条件为root = nullptr，也就是说当前遍历的结点是空了，所以本层递归就结束了，因为一个空树肯定不包含任何子树，返回false，如果找到了相等的两棵树，那就返回true；同时单层递归逻辑为如果往左或者往右递归，出现一样的即可，不要求全部一样。

class Solution {
public:
    bool isSameTree(TreeNode* left, TreeNode* right) {
        if(left==nullptr&&right!=nullptr) return false;
        else if(left!=nullptr&&right==nullptr) return false;
        else if(left==nullptr&&right==nullptr) return true;
        else if(left->val!=right->val) return false;

        bool comleft = isSameTree(left->left, right->left);
        bool comright = isSameTree(left->right, right->right);
        bool Issame = comleft && comright;
        return Issame;
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root==nullptr) return false;
        if(isSameTree(root,subRoot))
            return true;
        bool left = isSubtree(root->left, subRoot);
        bool right = isSubtree(root->right, subRoot);
        return (left||right);
    }
};

? ? ? ? 今天练习的很多二叉树的递归，主要还是得熟练掌握三要素法列写递归代码。