二叉树

110. 平衡二叉树

参考：代码随想录

思路

二叉树的深度：从根节点出发到该节点的最长简单路径边的条数。
二叉树的高度：从该节点出发到叶子节点的最长简单路径的条数。
题目要求判断是否是高度平衡的二叉树， 那么就是二叉树高度的问题，既然是求高度问题使用后序遍历。

递归

1. 递归函数的参数和返回值：var getHeight func(*TreeNode) int
2. 递归的终止条件：if node == nil ; return
3. 单层递归的逻辑：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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. 二叉树的所有路径

参考：代码随想录

思考

求二叉树的所有路径，就是记录从根节点到叶子节点到所有路径。需要使用前序遍历这样可以让父节点指向孩子节点。
在遍历的过程中，需要进行回溯操作，回退一个路径进入下一个路径之中。

递归

1. 确定递归函数参数和返回值: var traversal func(*TreeNode, []string)
2. 递归的结束条件：遇到了叶子节点if node.Left == nil && node.Right == nil {...}
3. 单层递归的处理逻辑：
   • 因为是前序遍历，要先处理节点逻辑，遇到叶子节点将路径加入到结果集中。
   • 如果左或右子节点不为空，进入下一个递归
   • 递归完之后还需要进行回溯操作，因为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 {}

递归

使用递归求解需要使用后序遍历，因为是求左叶子之和就必须把左右孩子返回的结果进行相加。

1. 确定递归函数的参数和返回值： func sumOfLeftLeaves(root *TreeNode) int,题目的函数就满足递归函数
2. 递归的终止条件：当前的节点为空，或者节点的左右节点都为空。
3. 单层递归的逻辑：遇到左叶子节点时，记录数值，然后通过递归求左子树的左叶子之和以及右子树的左叶子之和，最后进行相加

整体递归代码如下：

/**
 * 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
}

总结

通常情况下我们都是通过本节点的左右孩子判断本节点，但本题是通过父节点来进行判断的。

原文地址：http://www.cnblogs.com/neilliu/p/16786297.html