题面
判断给定二叉树是否对称。
Note : empty tree is valid.
算法
1. 根节点判空,若空,则返回true;(空树对称)
2. 根节点不空,递归判断左右子树。如果左右孩子都空,说明到了叶子,返回true;不都空而且一空一不空,返回false;都不空,且值不等,返回false,值相等,递归(左的左, 右的右) && (左的右, 右的左)
源码
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */
1 class Solution { 2 public: 3 bool isSymmetric(TreeNode* root) { 4 if(root == nullptr) 5 return true; 6 else 7 return Symmetric(root->left, root->right); 8 } 9 10 bool Symmetric(TreeNode* left, TreeNode* right) 11 { 12 if(left == nullptr && right == nullptr) 13 return true; 14 else if (left == nullptr || right == nullptr) 15 return false; 16 if(left->val == right->val) 17 return Symmetric(left->left, right->right) && Symmetric(left->right, right->left); 18 else 19 return false; 20 21 return true; 22 } 23 };