一、简介

给定一个二叉树，检查它是否是镜像对称的。

示例：

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

    1
   / \
  2   2
 / \ / \
3  4 4  3

二、递归法

如果跟节点为空，则树是对称的;

如果跟节点不为空，左右子树对称，则树是对称的;

怎么判断左右子树是否对称呢？

如果左树的左孩子与右树的右孩子对称，且左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。

实现如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    
    return checkSymmetric(root.Left, root.Right)
}

func checkSymmetric(left, right *TreeNode) bool {
    if left == nil && right == nil { // 左右子树为空
        return true
    } 
    
    if left == nil {// 左空 右非空
        return false
    }
    
    if right == nil { //右空 左非空
        return false
    }
    
    if left.Val != right.Val { // 左右节点值不相对
        return false
    }
    
    return checkSymmetric(left.Left, right.Right) && checkSymmetric(left.Right, right.Left)
}

三、迭代法

实现如下：

// 先进后出
type Stack struct {
	data []*TreeNode
}

func (s *Stack) Push(d *TreeNode) {
	if s.data == nil {
        s.data = make([]*TreeNode, 0)
	}

	s.data = append(s.data, d)
}

func (s *Stack) Pop() *TreeNode {
    dataLen := len(s.data)
	if dataLen == 0 {
		return nil
	}

	d := s.data[dataLen-1]
	s.data = s.data[:dataLen-1]

	return d
}

func (s *Stack) Len() int {
	return len(s.data)
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    
    if root.Left == nil && root.Right == nil {
        return true
    }
    
    if root.Left == nil  || root.Right == nil{
        return false
    }
    
    stack := new(Stack)
    stack.Push(root.Left)
    stack.Push(root.Right)
    
    for stack.Len() > 0 {
        right := stack.Pop()
        left := stack.Pop()
        
        if right == nil && left == nil {
            continue
        }
        
        if right == nil || left == nil {
            return false
        }
        
        if right.Val != left.Val {
            return false
        }
     
        stack.Push(left.Left)
        stack.Push(right.Right)
        
        stack.Push(left.Right)
        stack.Push(right.Left)
    }
    
    return true   
}