101. 对称二叉树
难度简单给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3]
是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3]
则不是镜像对称的:
1 / \ 2 2 \ \ 3 3
思路:利用递归从根节点开始,一个向左,一个向右,依次遍历,判断。
先判断好特殊情况,然后直接使用递归即可。
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * struct TreeNode *left; 6 * struct TreeNode *right; 7 * }; 8 */ 9 10 bool Symmetric(struct TreeNode* leftTree,struct TreeNode* rightTree) 11 { 12 if(leftTree==NULL&&rightTree==NULL){ 13 return true; 14 } 15 if(leftTree==NULL||rightTree==NULL){ 16 return false; 17 } 18 /*if(leftTree->val==rightTree->val){ 19 return Symmetric(leftTree->left,rightTree->right)&&Symmetric(leftTree->right,rightTree->left); 20 } 21 return false;*/这段代码功能与下面的返回功能一样,下面的是把上面这个给综合起来了。 22 return (leftTree->val==rightTree->val)&&Symmetric(leftTree->left,rightTree->right)&&Symmetric(leftTree->right,rightTree->left); 23 } 24 bool isSymmetric(struct TreeNode* root){ 25 return Symmetric(root,root); 26 }