用递归实现遍历法和分治法

摘要

递归Recursion，深搜DFS，回溯Backtracking的联系和区别
递归三要素是什么
通过二叉树学习DFS中的遍历法
什么是分治法，遍历法和分治法的区别
- 通过两道实战真题理解分治法和遍历法的区别

递归、深搜和回溯法的区别

递归 Recursion

递归函数：程序的一种实现方式，即函数进行了自我调用

递归算法：即大问题的结果依赖于小问题的结果，于是先用递归函数求解小问题
一般我们说递归的时候，大部分时候都在说递归函数而不是递归算法

深度优先搜索 Depth First Search

可以使用递归函数来实现

也可以不用递归函数来实现，如自己通过一个手动创建的栈 Stack 进行操作
深度优先搜索通常是指在搜索的过程中优先搜索深度更深的点而不是按照宽度搜索同层节点

回溯 Backtracking

回溯法：就是深度优先搜索算法

回溯操作：递归函数在回到上一层递归调用处的时候，一些参数需要改回到调用前的值，这个操作就是回溯，即让状态参数回到之前的值，递归调用前做了什么改动，递归调用之后都改回来

找点 vs 找路径

是否需要手动“回溯”的判断标准

找点，一般不需要回溯

func findNodes(node *TreeNode, nodes []*TreeNode) []*TreeNode {
	if node == nil {
		return nodes
	}
	nodes = append(nodes, node)
	nodes = findNodes(node.Left, nodes)
	nodes = findNodes(node.Right, nodes)
	return nodes
}

找路径，需要回溯，通过 append 和 pop

480 · 二叉树的所有路径

下面的实现每次递归调用时，会产生新的字符串拷贝

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// TreeNode 定义二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BinaryTreePaths 返回所有根到叶子节点的路径
func BinaryTreePaths(root *TreeNode) []string {
	if root == nil {
		return nil
	}
	paths := []string{}
	findPaths(root, "", &paths)
	return paths
}

// findPaths 是递归遍历二叉树的函数
func findPaths(node *TreeNode, path string, paths *[]string) {
	if node == nil {
		return
	}

	// 更新当前路径
	if len(path) > 0 {
		path += "->"
	}
	path += strconv.Itoa(node.Val)

	// 如果到达叶子节点，将路径加入结果集
	if node.Left == nil && node.Right == nil {
		*paths = append(*paths, path)
		return
	}

	// 递归处理左子树和右子树
	findPaths(node.Left, path, paths)
	findPaths(node.Right, path, paths)
}

func main() {
	// 创建一个示例二叉树
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Right: &TreeNode{
				Val: 5,
			},
		},
		Right: &TreeNode{
			Val: 3,
		},
	}

	// 输出所有路径
	paths := BinaryTreePaths(root)
	fmt.Println(paths) // 输出: ["1->2->5", "1->3"]
}

优化版本

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// TreeNode 定义二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BinaryTreePaths 返回所有根到叶子节点的路径
func BinaryTreePaths(root *TreeNode) []string {
	if root == nil {
		return nil
	}
	paths := []string{}
	path := []string{}
	findPaths(root, path, &paths)
	return paths
}

// findPaths 是递归遍历二叉树的函数
func findPaths(node *TreeNode, path []string, paths *[]string) {
	if node == nil {
		return
	}

	// 将当前节点的值添加到路径中
	path = append(path, strconv.Itoa(node.Val))

	// 如果到达叶子节点，将路径加入结果集
	if node.Left == nil && node.Right == nil {
		*paths = append(*paths, strings.Join(path, "->"))
		return
	}

	// 递归处理左子树和右子树
	findPaths(node.Left, path, paths)
	findPaths(node.Right, path, paths)

	// 回溯：递归结束后移除当前节点，回到上一个状态
	path = path[:len(path)-1]
}

func main() {
	// 创建一个示例二叉树
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Right: &TreeNode{
				Val: 5,
			},
		},
		Right: &TreeNode{
			Val: 3,
		},
	}

	// 输出所有路径
	paths := BinaryTreePaths(root)
	fmt.Println(paths) // 输出: ["1->2->5", "1->3"]
}

遍历法 vs 分治法

遍历法 = 一个小人拿着一个记事本走遍所有的节点
- 通常会用到一个全局变量或者是共享参数
分治法 = 分配小弟去做子任务，自己进行结果汇总
- 通常将利用 return value 记录子问题结果

二叉树上的分治法本质上也是在做遍历：后序遍历（先左右后根）

// 分治法
// 效率不高
func binaryTreePaths(node *TreeNode) []string {
	paths := []string{}
	if node == nil {
		return paths
	}
	if node.Left == nil && node.Right == nil {
		paths = append(paths, strconv.Itoa(node.Val))
		return paths
	}

	for _, leftPath := range binaryTreePaths(node.Left) {
		paths = append(paths, strconv.Itoa(node.Val)+"->"+leftPath)
	}
	for _, rightPath := range binaryTreePaths(node.Right) {
		paths = append(paths, strconv.Itoa(node.Val)+"->"+rightPath)
	}

	return paths
}

二叉树上的分治法模板

递归的定义
递归的拆解
递归的出口

// 分治法
func dnc(root *TreeNode) (res []string) {
	if root == nil {
		// 处理空树应该返回的结果
		return res
	}
	if root.Left == nil && root.Right == nil {
		// 处理叶子应该返回的结果
		// 如果叶子的返回结果可以通过两个空节点的返回结果得到
		// 就可以省略这一段代码
		return res
	}

	// 左子树返回结果
	resLeft := dnc(root.Left)
	// 右子树返回结果
	resRight := dnc(root.Right)
	// 整棵树的结果 = 按照一定方法合并左右子树的结果
	res = resLeft + resRight

	return res
}

93 · 平衡二叉树

给定一棵二叉树，判断是否是平衡的
平衡二叉树定义：任意节点左右子树高度之差不超过1

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/**
 * @param root: The root of binary tree.
 * @return: True if this Binary tree is Balanced, or false.
 */
func IsBalanced(root *TreeNode) bool {
	isBalanced, _ := divideConquer(root)
	return isBalanced
}

// 定义: 判断 root 为根的二叉树是否是平衡树并且返回高度是多少
func divideConquer(root *TreeNode) (bool, int) {
	// 出口
	if root == nil {
		return true, 0
	}

	// 拆解
	isLeftBalanced, leftHeight := divideConquer(root.Left)
	isRightBalanced, rightHeight := divideConquer(root.Right)
	rootHeight := max(leftHeight, rightHeight) + 1

	if !isLeftBalanced || !isRightBalanced {
		return false, rootHeight
	}
	if abs(leftHeight, rightHeight) > 1 {
		return false, rootHeight
	}
	return true, rootHeight
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func abs(a, b int) int {
	if a-b > 0 {
		return a - b
	} else {
		return -a + b
	}
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。