28. 对称的二叉树

题目链接

牛客

力扣

题目描述

解题思路

提供一个新的思路，但不一定保证正确。如果一棵二叉树是对称的，那么其中序遍历结果一定要先满足对称性，并且根节点在中序遍历结果数组的1/2位置，如果不满足一定非对称。但还需要注意，因为元素值可能重复，例如下图的情况，单纯靠遍历中序序列，可能存在对称的点并不是同一层的情况，所以需要在中序遍历中添加每一个遍历节点的层数，以此保证同层元素以根节点为分界线，向中序遍历数组两端一一对应。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    // 直接取中序遍历，从根节点对两边遍历分析
    ansArray = make([]Node,0)
    DFS(root,0)

    ansLen := len(ansArray)
    center := ansLen / 2
    for i:=0;i<center;i++ {
        if ansArray[i].val != ansArray[ansLen-1-i].val || ansArray[i].deep != ansArray[ansLen-1-i].deep {
            return false
        }
    }

    return true
}

type Node struct{
    val int
    deep int
}

var ansArray []Node

func DFS(root *TreeNode,deep int) {
    if root == nil {
        return
    }
    DFS(root.Left,deep+1)

    ansArray = append(ansArray,Node{val:root.Val,deep:deep})

    DFS(root.Right,deep+1)
}