对称二叉树

算法
留言

探索对称二叉树的多种判断方式

在二叉树的相关算法问题中，判断一棵二叉树是否为对称二叉树是一个经典的题目。本文将详细分析判断对称二叉树的多种方式，并对相应的代码实现进行深入解读。

一、对称二叉树的定义

对称二叉树是指一棵二叉树的左子树和右子树关于根节点对称。即左子树的左子节点与右子树的右子节点对称，左子树的右子节点与右子树的左子节点对称，并且对应节点的值相等。

二、递归法判断对称二叉树

（一）思路分析

递归法是一种直观且简洁的解决方式。我们可以定义一个递归函数，这个函数接收两棵子树作为参数，分别比较它们对应节点的值以及子树的结构。递归的终止条件有两个：一是当两棵子树都为空时，说明已经遍历到叶子节点的下一层，返回 true；二是当其中一棵子树为空，另一棵不为空，或者对应节点的值不相等时，返回 false。在递归过程中，我们需要分别比较左子树的左子节点与右子树的右子节点，以及左子树的右子节点与右子树的左子节点。

（二）代码实现

以下是使用递归法判断对称二叉树的代码示例：

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    return checkSymmetry(root.Left, root.Right)
}

func checkSymmetry(left *TreeNode, right *TreeNode) bool {
    // 递归终止条件
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil {
        return false
    }
    if left.Val!= right.Val {
        return false
    }
    // 递归比较左子树的左子节点与右子树的右子节点，以及左子树的右子节点与右子树的左子节点
    return checkSymmetry(left.Left, right.Right) && checkSymmetry(left.Right, right.Left)
}

三、迭代法（使用队列）判断对称二叉树

（一）思路分析

迭代法通常借助数据结构来辅助实现。这里我们使用队列来存储需要比较的节点对。首先将根节点的左子树和右子树入队。然后在循环中，每次取出队首的两个节点进行比较，如果它们都为空，则继续循环；如果其中一个为空，另一个不为空，或者节点值不相等，则返回 false。接着将左子树的左子节点与右子树的右子节点，以及左子树的右子节点与右子树的左子节点依次入队，直到队列为空，说明整棵树是对称的，返回 true。

（二）代码实现

以下是使用迭代法（队列）判断对称二叉树的代码示例，也就是题目中给出的代码：

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    queue := []*TreeNode{}
    queue = append(queue, root.Left)
    queue = append(queue, root.Right)
    for len(queue) > 0 {
        u, v := queue[0], queue[1]
        queue = queue[2:]
        if (u == nil && v == nil) {
            continue
        }
        if (u == nil || v == nil) {
            return false
        }
        if (u.Val!= v.Val) {
            return false
        }

        queue = append(queue, u.Left)
        queue = append(queue, v.Right)

        queue = append(queue, u.Right)
        queue = append(queue, v.Left)
    }
    return true
}

四、两种方法的比较

（一）时间复杂度

  • 递归法：在最坏的情况下，需要遍历二叉树的所有节点，时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点数。
  • 迭代法（队列）：同样需要遍历所有节点，每次入队和出队操作的时间复杂度都是常数级别的，所以总的时间复杂度也是 $O(n)$。

（二）空间复杂度

  • 递归法：由于递归调用需要使用栈空间，在最坏情况下，二叉树是一条链，递归深度为 $n$，所以空间复杂度为 $O(n)$。在最好情况下，二叉树是完全对称的，递归深度为树的高度 $log n$，空间复杂度为 $O(log n)$。
  • 迭代法（队列）：在最坏情况下，队列中最多会存储二叉树的一层节点，对于一棵满二叉树，其节点数最多为 $n/2$，所以空间复杂度为 $O(n)$。在最好情况下，二叉树是完全对称的，队列中最多存储树的高度个节点，空间复杂度为 $O(log n)$。

五、总结

判断对称二叉树可以使用递归法和迭代法（队列）。递归法代码简洁，易于理解，但可能会受到栈空间的限制。迭代法使用队列来模拟递归过程，虽然代码相对复杂一些，但在空间利用上可能会有一定的优势，尤其是在某些特定的二叉树结构下。在实际应用中，可以根据二叉树的特点以及对空间和时间复杂度的要求来选择合适的判断方法。

希望通过本文的分析，能够帮助读者深入理解对称二叉树的判断方式及其背后的算法思想，在解决相关二叉树问题时能够更加得心应手。