letecode [101] - Symmetric Tree
发布时间:2020-12-14 04:44:51 所属栏目:大数据 来源:网络整理
导读:Given a binary tree,check whether it is a mirror of itself (ie,symmetric around its center). For example,this binary tree [1,2,3,4,3] is symmetric: ??? 1 ?? / ? 2?? 2 ?/ / 3? 4 4? 3 ? But the following [1,null,3] is not: ??? 1 ?? /
Given a binary tree,check whether it is a mirror of itself (ie,symmetric around its center).
For example,this binary tree [1,2,3,4,3] is symmetric:
??? 1
?? / ? 2?? 2 ?/ / 3? 4 4? 3 ?
But the following [1,null,3] is not:
??? 1
?? / ? 2?? 2 ?? ?? ?? 3??? 3 题目大意:
给定一个二叉树,判断它是不是对称的(结构和值均对称相等)
理解:
1.先判断根节点,若为空,则为true;否则,若左右孩子为空,则为true,若左右孩子非空,则判断是否相等,相等则继续判断两个子树是否对称;其他情况均为false。
2.对于两个子树:
1)若root1左子节点和root2右子节点为空时,root1右子节点和root2左子节点为空,则对称;root1右子节点和root2左子节点非空且值相等,则继续递归比较(root1右子,root2左子);
2)若root1左子节点和root2右子节点非空时,root1右子节点和root2左子节点为空,则递归比较(root1左子,root2右子);root1右子节点和root2左子节点非空且值相等,则继续递归比较(root1左子,root2右子)和(root1右子,root2左子);
3)其他情况均为false。
理清这些条件判断语句,思路就清晰了。
代码C++:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x),left(NULL),right(NULL) {} * }; */ class Solution { public: bool isSymmetricLeftAndRight(TreeNode* root1,TreeNode* root2){ if(root1->left==NULL && root2->right==NULL){ if(root1->right==NULL && root2->left==NULL){ return true; }else if(root1->right!=NULL && root2->left!=NULL && root1->right->val==root2->left->val){ return isSymmetricLeftAndRight(root1->right,root2->left); }else{ return false; } }else if(root1->left!=NULL && root2->right!=NULL && root1->left->val==root2->right->val){ if(root1->right==NULL && root2->left==NULL){ return isSymmetricLeftAndRight(root1->left,root2->right); }else if(root1->right!=NULL && root2->left!=NULL && root1->right->val==root2->left->val){ return isSymmetricLeftAndRight(root1->left,root2->right)&isSymmetricLeftAndRight(root1->right,root2->left); }else{ return false; } }else{ return false; } } bool isSymmetric(TreeNode* root) { if(root==NULL) return true; if(root->left==NULL && root->right==NULL) return true; if((root->left!=NULL && root->right==NULL)||(root->left==NULL && root->right!=NULL)) return false; if(root->left->val == root->right->val){ return isSymmetricLeftAndRight(root->left,root->right); }else return false; } }; ?
运行结果:
? 执行用时 :?
16 ms 内存消耗 :?
14.8 MB
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |