Leetcode.101.Symmetric Tree

题目

给定一个二叉树, 判断这个二叉树是否对称.

Input: [1,2,2,3,4,4,3]
           1
          / \
         2   2
        / \ / \ 
       3  4 4  3
Output: true
Input: [1,2,2,null,3,null,3]
           1
          / \
         2   2
          \   \ 
           3   3
Output: false

思路

判断这个数是否对称: 将根节点的右边子树所有左右节点都交换位置就和根节点树一样.

因此可以递归, 将左树的左节点和右树的右节点比较, 左树的右节点和右树的左节点比较.

bool isTreeNodeEqual(TreeNode *left, TreeNode *right) {
    if(left == nullptr && right == nullptr) return true;
    if(left == nullptr || right == nullptr) return false;

    if (left->val != right->val) {
        return false;
    }

    if (isTreeNodeEqual(left->left, right->right) &&
        isTreeNodeEqual(left->right, right->left)) {
        return true;
    }

    return false;
}

// 将right树的left和right交换后和left相等
bool isSymmetric(TreeNode* root) {
    if(root == nullptr) return true;
    TreeNode *leftTree = root->left;
    TreeNode *rightTree = root->right;

    return isTreeNodeEqual(leftTree, rightTree);
}

总结

熟练运用递归, 考虑递归时的返回值使用.