二叉树
110. 平衡二叉树
思路
二叉树的深度：从根节点出发到该节点的最长简单路径边的条数。
二叉树的高度：从该节点出发到叶子节点的最长简单路径的条数。
题目要求判断是否是高度平衡的二叉树， 那么就是二叉树高度的问题，既然是求高度问题使用后序遍历。
递归
- 递归函数的参数和返回值：
var getHeight func(*TreeNode) int - 递归的终止条件：
if node == nil ; return - 单层递归的逻辑：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1，求出左右子树的差值，如果差值大于1则返回-1，表示当前已经不是平衡二叉树了。
leftH := getHeight(node.Left) // 左 if leftH == -1 { return -1 } rightH := getHeight(node.Right) // 右 if rightH == -1 { return -1 } if abs(leftH-rightH) > 1 { // 中 return -1 }
整体递归代码如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
var getHeight func(*TreeNode) int
getHeight = func(node *TreeNode) int {
if node == nil {
return 0
}
leftH := getHeight(node.Left) // 左
if leftH == -1 {
return -1
}
rightH := getHeight(node.Right) // 右
if rightH == -1 {
return -1
}
if abs(leftH-rightH) > 1 { // 中
return -1
}
return 1 + max(leftH, rightH)
}
return getHeight(root) != -1
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
迭代法
因为求二叉树的高度，因此无法使用层序遍历来完成，可以使用栈来模拟后序遍历求得节点的高度。然后再使用栈模拟后序遍历遍历左右子树判断是否是平衡二叉树。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
// 通过栈模拟的后序遍历 来求该节点的高度
var getDepth func(*TreeNode) int
getDepth = func(node *TreeNode) int {
if node == nil {
return 0
}
depth := 0
rlt := 0
stack := list.New()
stack.PushBack(node)
for stack.Len() > 0 {
e := stack.Back()
if e.Value != nil {
cur := e.Value.(*TreeNode)
stack.Remove(e)
depth++
stack.PushBack(cur)
stack.PushBack(nil)
if cur.Right != nil {
stack.PushBack(cur.Right)
}
if cur.Left != nil {
stack.PushBack(cur.Left)
}
} else {
stack.Remove(e)
stack.Remove(stack.Back())
depth--
}
if rlt < depth {
rlt = depth
}
}
return rlt
}
st := list.New()
st.PushBack(root)
for st.Len() > 0 {
node := st.Remove(st.Back()).(*TreeNode)
if abs(getDepth(node.Left)-getDepth(node.Right)) > 1 { //处理中间节点
return false
}
if node.Right != nil {
st.PushBack(node.Right)
}
if node.Left != nil {
st.PushBack(node.Left)
}
}
return true
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
总结
通过本题了解二叉树的深度和高度的区别，使用前序遍历求深度，使用后序遍历求高度。
257. 二叉树的所有路径
思考
求二叉树的所有路径，就是记录从根节点到叶子节点到所有路径。需要使用前序遍历这样可以让父节点指向孩子节点。
在遍历的过程中，需要进行回溯操作，回退一个路径进入下一个路径之中。
递归
- 确定递归函数参数和返回值:
var traversal func(*TreeNode, []string) - 递归的结束条件：遇到了叶子节点
if node.Left == nil && node.Right == nil {...} - 单层递归的处理逻辑：
- 因为是前序遍历，要先处理节点逻辑，遇到叶子节点将路径加入到结果集中。
- 如果左或右子节点不为空，进入下一个递归
- 递归完之后还需要进行回溯操作，因为path不能一直添加，还需要回退一个路径之后进入下一个路径。
递归代码如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func binaryTreePaths(root *TreeNode) []string {
rlt := []string{}
var traversal func(*TreeNode, []string)
traversal = func(node *TreeNode, paths []string) {
curVal := strconv.Itoa(node.Val)
paths = append(paths, curVal)
//左右子树为空
if node.Left == nil && node.Right == nil {
rlt = append(rlt, strings.Join(paths, "->"))
return
}
if node.Left != nil {
traversal(node.Left, paths)
paths = paths[:len(paths)-1] // 回溯
}
if node.Right != nil {
traversal(node.Right, paths)
paths = paths[:len(paths)-1] // 回溯
}
}
traversal(root, []string{})
return rlt
}
迭代法：
也可以使用栈来模拟前序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func binaryTreePaths(root *TreeNode) []string {
type pair struct {
node *TreeNode
path string
}
rlt := []string{}
stack := list.New()
stack.PushBack(pair{root, strconv.Itoa(root.Val)})
for stack.Len() > 0 {
p := stack.Remove(stack.Back()).(pair)
if p.node.Left == nil && p.node.Right == nil {
rlt = append(rlt, p.path)
}
if p.node.Right != nil {
stack.PushBack(pair{p.node.Right, p.path + "->" + strconv.Itoa(p.node.Right.Val)})
}
if p.node.Left != nil {
stack.PushBack(pair{p.node.Left, p.path + "->" + strconv.Itoa(p.node.Left.Val)})
}
}
return rlt
}
总结
求二叉树的所有路径问题需要注意回溯的问题， 递归与回溯操作应该放到同一个花括号内处理。
404. 左叶子之和
思考
根据题目描述二叉树的左叶子定义为：节点A的左孩子不为空，并且节点A的左孩子的左右子节点都为空，则称节点A的左孩子为左叶子节点。
求左叶子节点则需要根据父节点来进行判断。即：if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {}
递归
使用递归求解需要使用后序遍历，因为是求左叶子之和就必须把左右孩子返回的结果进行相加。
- 确定递归函数的参数和返回值：
func sumOfLeftLeaves(root *TreeNode) int,题目的函数就满足递归函数 - 递归的终止条件：当前的节点为空，或者节点的左右节点都为空。
- 单层递归的逻辑：遇到左叶子节点时，记录数值，然后通过递归求左子树的左叶子之和以及右子树的左叶子之和，最后进行相加
整体递归代码如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil && root.Right == nil {
return 0
}
leftSum := sumOfLeftLeaves(root.Left)
if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
leftSum = root.Left.Val
}
rightSum := sumOfLeftLeaves(root.Right)
return leftSum + rightSum
}
迭代法
使用迭代法处理的逻辑也是类似的，比较容易
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumOfLeftLeaves(root *TreeNode) int {
// 前序遍历
rlt := 0
stack := list.New()
stack.PushBack(root)
for stack.Len() > 0 {
cur := stack.Remove(stack.Back()).(*TreeNode)
if cur.Left != nil && cur.Left.Left == nil && cur.Left.Right == nil {
rlt += cur.Left.Val
}
if cur.Right != nil {
stack.PushBack(cur.Right)
}
if cur.Left != nil {
stack.PushBack(cur.Left)
}
}
return rlt
}
总结
通常情况下我们都是通过本节点的左右孩子判断本节点，但本题是通过父节点来进行判断的。
标签：node,Right,TreeNode,nil,第十七,算法,二叉树,return,Left From： https://www.cnblogs.com/neilliu/p/16786297.html