目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
二叉树对象是否对称
访问量:1784
一、简介
给定一个二叉树,检查它是否是镜像对称的。
示例:
二叉树 [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 }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助