判断是否对称二叉树_判断二叉树是否对称

二叉树具备天然的递归性，往往在处理二叉树的题目时，我们都需要去思考怎么样利用递归，想清楚能解决 50% 的二叉树问题。

• 有三点需要注意
  • 1、L.val = R.val：即此两对称节点值相等。
    
  • 2、L.left.val = R.right.val：即 L 的左子节点和 R 的右子节点对称。
    
  • 3、 L.right.val = R.left.val：即 L 的右子节点和 R 的左子节点对称。
• 明确以上三点就好办了
  从底至顶进行递归操作，判断每对节点是否对称，从而判断树是否为对称二叉树。

/// <summary>
/// 节点类
/// </summary>
internal class TreeNode
{
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }
    public int Val { get; set; }

	/// <summary>
	/// 构造器
	/// </summary>
	/// <param name="val">数据域</param>
	/// <param name="left">左节点</param>
	/// <param name="right">右节点</param>
    public TreeNode(int val, TreeNode left = null, TreeNode right = null)
    {
        Left = left;
        Right = right;
        Val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

实现类

internal class BinaryTree
{
    public bool IsSymmetric(TreeNode root)
    {
        // 边界情况
        if (root is null) return true;
        // 递归判断左子树和右子树是否对称
        return IsSymmetriacalCore(root.Left, root.Right);
    }

    private bool IsSymmetriacalCore(TreeNode L, TreeNode R)
    {
        // 如果某根子树的左右两子树同时为空，肯定是对称的，直接返回 true
        if (L is null && R is null) return true;

        // 说明根子树的左右两子树有某子树为空，某子树有值，不对称，返回 false
        if (L is null || R is null) return false;

        // 左子树的值与右子树的值不相等，不对称，返回 false
        if (L.Val != R.Val) return false;

        // 递归的对比当前节点的左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树是否对称
        return IsSymmetriacalCore(L.Left, R.Right) && IsSymmetriacalCore(L.Right, R.Left);
    }
}
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