对称二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：如果二叉树为镜像二叉树，则遍历：(根,左结点,右结点 ) 与 (根,右结点，左结点)遍历顺序相同，否则不是镜像二叉树。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if (pRoot == NULL) {
            return true;
        }
        vector<int>left;
        vector<int>right;
        leftProOrder(pRoot,left);
        rightProOrder(pRoot,right);
        if (left == right) {
            return true;
        }
        else
        {
            return false;
        }
    }
    //根、左、右
    void leftProOrder(TreeNode* pRoot, vector<int>&data) {
        if (pRoot == NULL) {
            /*
            这里添加元素是用来记录空结点的位置，用来对比确定是否为镜像二叉树
            */
            data.push_back(0);
            return;
        }
        data.push_back(pRoot->val);
        leftProOrder(pRoot->left,data);
        leftProOrder(pRoot->right, data);
    }
    //根、右、左
    void rightProOrder(TreeNode* pRoot, vector<int>&data) {
        if (pRoot ==NULL) {
            /*
            这里添加元素是用来记录空结点的位置，用来对比确定是否为镜像二叉树
            */
            data.push_back(0);
            return;
        }
        data.push_back(pRoot->val);
        rightProOrder(pRoot->right,data);
        rightProOrder(pRoot->left,data);
    }
};

如果遍历时poot==NULL时，集合中不添加元素，则无法判断二叉树左右结点的位置，如下图：