对称的二叉树——二叉树,递归

November 01, 2021

题目:

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

二叉树-1
    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

二叉树-2
    1
   / \
  2   2
   \   \
   3    3

示例:

示例一:

输入:root = [1,2,2,3,4,4,3]
输出:true

示例二:

输入:root = [1,2,2,null,3,null,3]
输出:false

限制:

0 <= 节点个数 <= 1000

思路

检测中序遍历后的序列

观察题目之后,第一个想到的思路是将二叉树中的数字按照中序遍历添加到一个数组中,由于中序遍历的特点,数组中间的元素是树的根节点,左侧是左子树生成的中序遍历数组,右边是右子树生成的中序遍历数组。一颗对称的树所生成的数组左右两侧是对称的,可以用类似检测回文的方式检测该数组,来达到检测对称二叉树的目的。

例如,对于上文中的二叉树-1,中序遍历之后生成的数组为以下顺序。

3 -> 2 -> 4 -> 1 -> 4 -> 2 -> 3

具体做法是:在数组的前后设置双指针,检测两个指针指向的数字是否相等,如果不相等则不是对称二叉树,直到两个指针重合。

后来发现这种检测方式是不严谨的,一个明显的反例。有一棵二叉树如下所示:

二叉树-3
    5
   / \
  4   1
   \   \
   1    4
  /    /
 2    2

对于二叉树-3,中序遍历之后生成的数组为以下顺序。

4 -> 2 -> 1 -> 5 -> 1 -> 2 -> 4

这个数组是明显是左右对称的,但是生成它的二叉树也明显不是对称二叉树。这是因为不同的二叉树中序遍历的结果可能是相同的,而且有很多种情况。所以这个思路行不通。

递归检测左右子树

观察对称二叉树的结构,可以发现,对称的关键是根节点的左子树和右子树互为镜像,而两个树互为镜像需要满足的条件是:

  1. 都为 null 的两棵树互为镜像。
  2. 两棵树中只有一棵树为 null,则这两棵树不互为镜像。
  3. 根节点的值相同
  4. A 树的左子树与 B 树的右子树互为镜像。
  5. A 树的右子树与 B 树的左子树互为镜像。

问题拆分之后,有了递归的结构。这样可以把以上的规则对应到递归问题框架的每个步骤中:

  • 递归终止:1,2。
  • 处理当前节点:3。
  • 缩减问题规模,解决子问题:4,5。

图解

要点:

  • 每个递归函数要处理的是两个树的根节点,而在一般的二叉树问题中,每个递归函数往往只用处理单个节点,虽然处理的节点数量不同,但是基本的原则是一致的:处理当前层级,拆分出当前问题的子问题,求解子问题,根据子问题的解计算出当前问题的解。
  • 谨慎处理递归退出条件。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var isSymmetric = function (root) {
    if (!root) return true;
    return dfs(root.left, root.right);

    function dfs(treeLeft, treeRight) {
        // 处理递归终止条件
        if (!treeLeft && !treeRight) return true;
        if (!(treeLeft && treeRight)) return false;
        // 处理当前节点
        if (treeLeft.val !== treeRight.val) return false;
        // 递归处理子节点
        return dfs(treeLeft.left, treeRight.right)
            && dfs(treeLeft.right, treeRight.left);
    }
};

相关阅读


Profile picture

这里是要没时间了

职业是前端开发,早餐喜欢吃 711 的芝士猪排饭团。喜欢写代码,爱折腾

© 2021, 分享知识和生活,记录成长与感动。