二叉树
226. 翻转二叉树
思路
翻转二叉树的方式：
- 递归
- 迭代法
- 层序遍历
1.递归
前序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
// 递归前序遍历
root.Left, root.Right = root.Right, root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
}
后序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
// 递归后序遍历
invertTree(root.Left)
invertTree(root.Right)
root.Left, root.Right = root.Right, root.Left
return root
}
中序遍历
因为中序遍历的顺序是左中右，按照前后序的方式来处理的话会导致节点多次反转的问题。
解决办法：左子树翻转一次后回退到中间节点，中间节点再次翻转，此时的左子树变成了右子树，右子树变成了左子树，此时只需要再处理一次左子树（翻转前的右子树）。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
// 递归中序遍历
invertTree(root.Left)
root.Left, root.Right = root.Right, root.Left
invertTree(root.Left)
return root
}
2.迭代法
以下代码使用前序遍历的方式，后序遍历也类似。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
// 前序遍历
if root == nil {
return root
}
stack := list.New()
stack.PushBack(root)
for stack.Len() > 0 {
e := stack.Back()
if e.Value != nil {
cur := e.Value.(*TreeNode)
stack.Remove(e)
if cur.Right != nil {
stack.PushBack(cur.Right)
}
if cur.Left != nil {
stack.PushBack(cur.Left)
}
stack.PushBack(cur)
stack.PushBack(nil)
} else {
stack.Remove(e)
cur := stack.Remove(stack.Back()).(*TreeNode)
cur.Left, cur.Right = cur.Right, cur.Left
}
}
return root
}
3.层序遍历
使用层序遍历，翻转每一层的各个节点
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
queue := list.New()
queue.PushBack(root)
for queue.Len() > 0 {
length := queue.Len()
// 处理每一层的各个节点
for ; length > 0; length-- {
cur := queue.Remove(queue.Front()).(*TreeNode)
cur.Left, cur.Right = cur.Right, cur.Left // 交换
if cur.Left != nil {
queue.PushBack(cur.Left)
}
if cur.Right != nil {
queue.PushBack(cur.Right)
}
}
}
return root
}
总结
翻转二叉树可以有多种实现方式，递归的方式容易理解和实现。但是不建议使用中序遍历容易造成错误。
迭代的方法中可以模拟深度优先搜索和广度优先搜索。
101. 对称二叉树
思路
判断二叉树是否对称，需要将树的左子树的左节点与右子树的右节点对比，左子树的右节点与右子树的左节点进行对比。
使用递归
- 确定递归函数参数与返回值
func dfs(left *TreeNode, right *TreeNode) bool - 确定递归终止条件
- 左右节点都为空，则
true - 左右有一个不为空，则
false - 左右都不为空，但数值不相等
- 左右节点都为空，则
- 单层递归逻辑
- 比较左子树的左节点与右子树的右节点
- 比较左子树的右节点与右子树的左节点
- 左右都为
true, 返回true, 否则false
递归
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
return dfs(root.Left, root.Right)
}
func dfs(left *TreeNode, right *TreeNode) bool {
// 左子树为空 右子树为空
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
if left.Val != right.Val {
return false
}
outer := dfs(left.Left, right.Right) // 左子树： 左 右子树： 右
inner := dfs(left.Right, right.Left) // 左子树： 右 右子树： 左
return outer && inner // 左子树： 中 右子树： 中
}
迭代法
使用队列判断左右子树是否相等
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
if root == nil {
return false
}
queue := list.New()
queue.PushBack(root.Left)
queue.PushBack(root.Right)
for queue.Len() > 0 {
//从队列中取出
leftNode := queue.Remove(queue.Front()).(*TreeNode)
rightNode := queue.Remove(queue.Front()).(*TreeNode)
if leftNode == nil && rightNode == nil { // 此时对称
continue
}
if leftNode == nil || rightNode == nil || (leftNode.Val != rightNode.Val) {
return false
}
queue.PushBack(leftNode.Left) // 加入左节点左孩子
queue.PushBack(rightNode.Right) // 加入右节点右孩子
queue.PushBack(rightNode.Left) // 加入右节点左孩子
queue.PushBack(leftNode.Right) // 加入左节点右孩子
}
return true
}
总结
以上代码不是最简单的形式，但是思路比较清晰易于理解。迭代法就是将左右子树依次放到队列中，然后依次取出进行比对。按照此思路使用栈也是可以处理的。
标签：Right,TreeNode,cur,第十五天,queue,算法,二叉树,root,Left From： https://www.cnblogs.com/neilliu/p/16777906.html