LeetCode101—Symmetric Tree

た入场券 2022-08-21 03:24 15阅读 0赞

# LeetCode101—Symmetric Tree #

## 原题 ##

> Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
> 
> For example, this binary tree is symmetric:
> 
> 　　　　1  
> 　　　/　　\\  
> 　　2　　　　2  
> 　/ 　\\　　　/　\\  
> 3　　　4　4　　　3  
> But the following is not:  
> 　　　　1  
> 　　　/　　\\  
> 　　2　　　　2  
> 　　　\\　　　　＼  
> 　　　　3　　　　３

判断一棵树是否“对称”

## 分析 ##

这种树的结构实在太特殊了，就把第一个示例的先序、中序、后序遍历的结果都写了出来，并没有发现什么规律，但是仔细一想，既然是对称的，那么左右子树是可以互换的，也就是说递归的时候也可以互换：以先序遍历来说，访问根->递归访问左子树->递归访问右子树；互换其左右子树也就是：访问根->递归访问右子树->递归访问左子树。两种情况的结果一致。当然可能有更方便的办法，等哪天学习了再补充。

## 代码 ##

class Solution {
    private:
        void dfs(TreeNode* root,vector<int >&result)//先序遍历（根->左子树->右子树）
        {
            if (root == NULL)
            {
                result.push_back(-1);
                return;
            }
            result.push_back(root->val);
            dfs(root->left, result);
            dfs(root->right, result);
        }
        void dfsr(TreeNode* root, vector<int >&result)//先序遍历（根->右子树->左子树）
        {
            if (root == NULL)
            {
                result.push_back(-1);
                return;
            }
            result.push_back(root->val);
            dfsr(root->right, result);
            dfsr(root->left, result);
        }
    public:
        bool isSymmetric(TreeNode* root) {
            vector<int>res1;
            vector<int>res2;
            dfs(root, res1);
            dfsr(root, res2);
            return equal(res1.cbegin(), res1.cend(), res2.cbegin());
        }
    };