对称的二叉树

题意

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

样例

A). 3               
   / \
  1   1
 / \ / \
6  4 4  6         

B). 3
   / \
  1   2
 / \ / \
7  4 5  6 

A 与 B 在结构上都是对称的,但是本题的题意是指也对应,所以 A 树是一颗对称二叉树,B 树不是一颗对称的二叉树。

思路

观察上方的样例可得结论:

  • 根节点的左右节点的值是相同的
  • 除根节点外,某节点的右子树与兄弟节点的左子树的值相同
  • 除根节点外,某节点的左子树与兄弟节点的右子树的值相同

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if (pRoot == null) {
return true;
}

return fun(pRoot.left, pRoot.right);

}
boolean fun(TreeNode n1, TreeNode n2) {
if (n1 == null && n2 == null){
return true;
}

if (n1 != null && n2 != null) {
return n1.val == n2.val && fun(n1.left, n2.right) && fun(n1.right, n2.left);
}

return false;
}

}

原题地址

牛客网:对称的二叉树

坚持原创技术分享,您的支持将鼓励我继续创作!