leetcode 101. 对称二叉树 递归解法 c语言

如题：

给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [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

这道题刚开始想到的是使用队列+BFS，因为c语言里没有现成的队列数据结构，需要自己实现，嫌麻烦。换个方式，看了示例1，觉得中序遍历得到恰是一个首尾对称的序列，写好代码提交运行出错，中序遍历情况下示例2那种类型也是对称的，但不符合题目要求。后来采用递归方式，镜像对称，根节点不必说，只要两颗子树对称就好。递归遍历子树，双方各提供一个对称节点进行比较，例如左子树提供左孩子，右子树提供右孩子以及左子树提供。方法非常巧妙精简，下面是c语言的解法：

//递归遍历bool isMirror(struct TreeNode* left, struct TreeNode* right){if (left == NULL && right == NULL)return 1;else if (!left || !right)return 0;else{//分别遍历左右子树的左孩子和右孩子if (left->val == right->val)return (isMirror(left->left, right->right) && isMirror(left->right, right->left));return 0;}}bool isSymmetric(struct TreeNode* root){return isMirror(root, root);}

=============================================================================================

Linux应用程序、内核、驱动开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。