对称的二叉树

Posted on Edited on In Views: Waline: Views: Symbols count in article: 433 Reading time ≈ 1 mins.

题解方法

  • 广度优先搜索
  • 递归

镜像判断

  • 当前节点的左右节点的值相同
  • 当前节点的左子树与右子树镜像对称

广度优先搜索

终止条件

  • 左右节点均为 null，返回 true
  • 左右节点仅有一个为 null，返回 false

搜索路径

  1. 从根节点出发，使用两个指针分别指向左右节点
  2. 递归判断左指针的左节点与右指针的右节点以及左指针的右节点与右指针的左节点的对称性

核心代码

广度优先搜索

1
2
3
4
5
6
7
8
9
10
public boolean bfs(TreeNode p, TreeNode q) {
    if (null == p && null == q) {
        return true;
    }
    if (null == p || null == q) {
        return false;
    }

    return p.val == q.val && bfs(p.left, q.right) && bfs(p.right, q.left);
}

题目来源