CC面试经典案例对称二叉树的判断

前言

二叉树作为C/C++软件工程师必须掌握的内容，在面试过程中经常遇到。本文以对称二叉树的判断方法为例，对二叉树部分的内容进行简要介绍。

对称二叉树的判断

示例案例：给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）例如：下面这棵二叉树是对称的

而下面这棵二叉树不对称。

测试用例

输入：

{1,2,2,3,4,4,3}

返回值：

true

输入：

{8,6,9,5,7,7,5}

返回值：

false

代码设计：从题目的描述我们不难看出，满足条件的二叉树必须满足以下条件——同一深度下，左节点的值和右键点的值必须相等；左右子节点的深度必须相同，否则对应的二叉树就不是对称的二叉树。如下图所示：

根据上述要求我们不难得出以下代码：

structTreeNode{intval;structTreeNode*left;structTreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};classSolution{public:boolsameCompare(TreeNode*root1,TreeNode*root2){if(root1==nullptrroot2==nullptr)　　//二叉树的左右子//节点深度必须相同returntrue;if(root1==nullptr

root2==nullptr)//二叉树的左右子节点//深度必须相同，否则就不对称returnfalse;if(root1-val!=root2-val)　　　　//同一深度下左右//节点的值必须相等，否则二叉树部队称returnfalse;returnsameCompare(root1-left,root2-right)sameCompare(root1-right,root2-left);　　　　//对于符//合条件的二叉树进行递归}boolisSymmetrical(TreeNode*pRoot){returnsameCompare(pRoot,pRoot);}};

转载请注明：http://www.aierlanlan.com/grrz/4024.html