首页 > 代码库 > [LeetCode 题解]: Symmetric Tree

[LeetCode 题解]: Symmetric Tree

2024-07-15 19:19:09   217人阅读

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1   /   2   2 / \ / 3  4 4  3

 

But the following is not:

    1   /   2   2   \      3    3

 

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


OJ‘s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.

Here‘s an example:

   1  /  2   3    /   4         5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
 
题意：
给定一颗二叉树，判断该树是否为左右对称的二叉树。
思路：
（1）如果一棵树仅含有一个节点，那么这个树必定是对称的。
　　例如：  1
（2）如果某个节点，只有左子树或者右子树，那么该树不是对称的。
　　例如： 1　　　　　　　　1　　　　　　　　　　1
　　　　　/　　　　或 　　　　\ 　　　　或　　　 /    \
　　　　2　　　　　　　　　　　2　　　　　　　 2　  2
　　　　　　　　　　　　　　　　　　　　　　　/  \
　　　　　　　　　　　　　　　　　　　　　　 4    4
（3）如果某个节点，左右孩子都存在，那么递归比较：
         左孩子的左孩子 是否等于 右孩子的右孩子。
         左孩子的右孩子 是否等于 右孩子的左孩子。
class Solution {public:    bool isSymmetric(TreeNode *root){        return root? Symmetric(root->left,root->right):true;    }    bool Symmetric(TreeNode *left, TreeNode *right){        if(left==NULL && right==NULL) return true;// 左右孩子为空        if(!left || !right) return false; // 仅含有左子树或者右子树            return left->val == right->val            && Symmetric(left->left,right->right)            && Symmetric(left->right,right->left);    }};

转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！


联系
我们