首页 > 代码库 > LeetCode OJ Symmetric Tree 判断是否为对称树（AC代码）
LeetCode OJ Symmetric Tree 判断是否为对称树（AC代码）
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 bool isSymmetric(TreeNode *root) {13 if(!root) 14 return true; //无根结点15 else if(root->left==(void*)0 && root->right==(void*)0) //只有根结点的树16 return true;17 else if(root->left!=(void*)0 && root->right!=(void*)0 && isSymmetric(root->left,root->right)) //两个子树非空,左右子树为对称18 return true;19 else20 return false;21 }22 bool isSymmetric(TreeNode *left,TreeNode *right) {23 if(left->val==right->val){ //左右结点值相等24 if(left->left==(void*)0 && right->right==(void*)0 || left->left!=(void*)0 && right->right!=(void*)0 && isSymmetric(left->left,right->right)){ //左右子树都为空、或者对称25 if(left->right==(void*)0 && right->left==(void*)0 ||left->right!=(void*)0 && right->left!=(void*)0 && isSymmetric(left->right,right->left)) //右左子树都为空、或对称26 return true;27 else28 return false;29 }30 else //左右子树不对称31 return false;32 }33 else //左右结点值不等34 return false;35 }36 };
本题有多种解法，递归的，非递归的。
而上面代码是递归法。
思路：
主要判断左子树与右子树。
在判断左时，循环下去肯定会到达叶子结点中最左边的结点与最右边的结点比较。
到了这一步因为他们都没有左（右）子树了，所以得开始判断这两个结点的右（左）子树了。
当某个结点对称了，它的左子树也对称了，右子树也对称了，那才是真的对称了。
LeetCode OJ Symmetric Tree 判断是否为对称树（AC代码）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。