对称的二叉树

发表于

描述
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

例如:

  • 对称二叉树
  • 非对称二叉树

题解

二叉树递归

  • 终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回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
27
28
package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/**
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
*/
func isSymmetrical( pRoot *TreeNode ) bool {
    // write code here
    return isSame(pRoot, pRoot)
}

func isSame(left, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    }
    if (left == nil && right != nil) || (left != nil && right == nil) {
        return false
    }

    return left.Val == right.Val && isSame(left.Left, right.Right) && isSame(left.Right, right.Left)
}