假设二叉树采用三叉链式,二叉树例题解析

　　请实现一个判断二叉树是否对称的函数。

　　如果一棵二叉树与其镜像相同，那么它就是对称的。

　　样品

　　如下图所示，二叉树[1，2，2，3，4，4，3，空，空，空，空，空]是对称二叉树：

　　一个

　　/\

　　2 2

　　/\/\

　　3 4 4 3

　　如下图所示，二叉树[1，2，2，null，4，4，3，null，null，null，null]不是对称二叉树：

　　一个

　　/\

　　2 2

　　\/\

　　4 3个想法(二叉树，递归)

　　确定两个递归子树是否互为镜像。

　　两个子树相互镜像当且仅当：

　　两个子树的根节点值相等；第一子树的左子树和第二子树的右子树互为镜像，第一子树的右子树和第二子树的左子树互为镜像；时间复杂度

　　每个节点从上到下只遍历一次，所以时间复杂度为。

　　代码/* *

　　*二叉树节点的定义。

　　*结构树节点{

　　* int val

　　* TreeNode * left

　　* TreeNode * right

　　* TreeNode(int x) : val(x)，left(NULL)，right(NULL) {}

　　* };

　　*/

　　类别解决方案{

　　公共：

　　bool is symmetric(TreeNode * root){

　　如果(！root)返回true//根节点为空，返回true

　　返回dfs(根左，根右)；//确定两个子树是否互为镜像

　　}

　　bool dfs(TreeNode* p，TreeNode* q){

　　如果(！p！q)返回true//两个节点都是空的

　　else if(！p！q)返回false//只有一个是空的。

　　如果(p- val！=q- val)返回false

　　//第一子树的左子树和第二子树的右子树相互镜像，第一子树的右子树和第二子树的左子树相互镜像；

　　返回dfs(p-左，q-右)dfs(p-右，q-左)；

　　}

　　};

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。