面试过程中，经常会被问到二叉树的遍历、从根节点到各叶子节点所有路径、是否存在某条路径和为某个值等算法题。
针对这些题，都可以使用二叉树的深度优先遍历模板加以解决。
使用深度优先遍历，将从根节点到叶子节点经过的路径的值放在path切片中，当到达叶子节点时将各路径放入二维切片的指针变量res中，然后递归调用左子树、右子树。
// 深度优先遍历（递归实现方式）
// 注意：这里path一维切片不能用指针类型，二维切片使用指针类型的切片，否则得不到想要的结果
func dfsPaths(curNode *TreeNode, path []int, res *[][]int) {
if curNode == nil {
return
}
path = append(path, curNode.Val)
// 达到叶子节点，将根节点到叶子节点组成的路径加入res结果集 （这里使用append([]int{}, path...)
// 将path切片中的路径复制过去再添加到res，不需要再对path回溯：path=path[:len(path）-1
if curNode.Left == nil && curNode.Right == nil {
*res = append(*res, append([]int{}, path...))
}
// 递归左子树、右子树
dfsPaths(curNode.Left, path, res)
dfsPaths(curNode.Right, path, res)
}
leetcode相关题型
面试时，常见的算法题，绝大部分都来自《剑指Offer》、LeetCode刷题网站。现在从中选择几道题，使用上面的模板加以解决。
leetcode 257. 二叉树的所有路径链接：https://leetcode-cn.com/problems/binary-tree-paths/
题目描述给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]
示例 2：
输入：root = [1]
输出：[“1”]
// 返回从根节点到各个叶子节点上所有路径组成的字符串数组
func binaryTreePaths(root *TreeNode) []string {
if root == nil {
return nil
}
var (
path []int
pathSet [][]int
)
dfsPaths(root, path, &pathSet)
return convertPathString(pathSet)
}
// 深度优先遍历（递归实现方式）
// 注意：这里path一维切片不能用指针类型，二维切片使用指针类型的切片，否则得不到想要的结果
func dfsPaths(curNode *TreeNode, path []int, res *[][]int) {
if curNode == nil {
return
}
path = append(path, curNode.Val)
// 达到叶子节点，将根节点到叶子节点组成的路径加入res结果集 （这里使用append([]int{}, path...)
// 将path切片中的路径复制过去再添加到res，不需要再对path回溯：path=path[:len(path）-1
if curNode.Left == nil && curNode.Right == nil {
*res = append(*res, append([]int{}, path...))
}
// 递归左子树、右子树
dfsPaths(curNode.Left, path, res)
dfsPaths(curNode.Right, path, res)
}
// 将路径组成的二维数组转换为一维切片字符串
func convertPathString(pathSet [][]int) []string {
var res []string
for _, r := range pathSet {
var temp string
for n, c := range r {
if n == len(r)-1 {
temp += fmt.Sprintf("%d", c)
} else {
temp += fmt.Sprintf("%d->", c)
}
}
res = append(res, temp)
}
return res
}
leetcode 988. 从叶结点开始的最小字符串
链接：https://leetcode-cn.com/problems/smallest-string-starting-from-leaf/
题目描述给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 ‘a’ 到 ‘z’：值 0 代表 ‘a’，值 1 代表 ‘b’，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 “ab” 比 “aba” 要小。叶结点是指没有子结点的结点。）
示例 1：
输入：[0,1,2,3,4,3,4]
输出：“dba”
示例 2：
输入：[25,1,3,1,3,0,2]
输出：“adz”
示例 3：
输入：[2,2,1,null,1,0,null,0]
输出：“abc”
var (
// 数字与字母的映射
m = map[int]string{0:"a", 1: "b", 2:"c", 3:"d", 4:"e", 5:"f",
6:"g", 7:"h", 8:"i", 9:"j", 10:"k", 11:"l",
12:"m", 13:"n", 14:"o", 15:"p", 16:"q", 17:"r",
18:"s", 19:"t", 20:"u", 21:"v", 22:"w", 23:"x", 24:"y", 25:"z"}
)
func smallestFromLeaf(root *TreeNode) string {
if root == nil {
return ""
}
var (
path []int
pathSet [][]int
)
dfsPaths(root, path, &pathSet)
resSet := reversePathString(pathSet)
sort.Strings(resSet)
return resSet[0]
}
func dfsPaths(root *TreeNode, path []int, res *[][]int) {
if root == nil {
return
}
path = append(path, root.Val)
if root.Left == nil && root.Right == nil {
*res = append(*res, append([]int{}, path...))
}
dfsPaths(root.Left, path, res)
dfsPaths(root.Right, path, res)
}
func reversePathString(pathSet [][]int) []string{
var res []string
for _, r := range pathSet {
temp := ""
for i := len(r)-1; i >= 0; i-- {
temp += m[r[i]]
}
res = append(res, temp)
}
return res
}
leetcode 129. 求根节点到叶节点数字之和
题目链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
题目描述给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
示例 2：
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026
func sumNumbers(root *TreeNode) int {
var (
sum int
path []int
pathSet [][]int
)
dfsPaths(root, path, &pathSet)
arr := pathHandler(pathSet)
for _, v := range arr {
sum += v
}
return sum
}
func dfsPaths(root *TreeNode, path []int, res *[][]int) {
if root == nil {
return
}
path = append(path, root.Val)
if root.Left == nil && root.Right == nil {
*res = append(*res, append([]int{}, path...))
}
dfsPaths(root.Left, path, res)
dfsPaths(root.Right, path, res)
}
func pathHandler(pathSet [][]int) []int {
res := make([]int, 0)
for _, r := range pathSet {
temp := 0
for _, c := range r {
temp = temp * 10
temp += c
}
res = append(res, temp)
}
return res
}
leetcode 112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
可以使用上面的模板，将从根节点到各叶子节点所经过路径上的值添加到path路径切片，到叶子节点后将路径path切片添加到res二维切片，然后计算res中的各一维路径切片的和sum，如果sum == target则返回true，否则返回false。
还可以使用如下递归的方式实现：
func hasPathSum(root *TreeNode, sum int) bool {
if(root == nil) { // 根为空，肯定不存在
return false
}
if(root.Left == nil && root.Right == nil && sum == root.Val) { // 当前节点到达叶子节点（其左右子节点都为nil），并且这条路径剩余节点之和为0（sum - root.Val == 0即sum==root.Val），则存在这样一条路径
return true
}
leftHas := hasPathSum(root.Left, sum - root.Val) // 递归地看根的左子树是否存在和为sum - root.Val的路径
rightHas := hasPathSum(root.Right, sum - root.Val) // 递归地看根的右子树中是否存在和为sum减去根节点值的路径
return leftHas || rightHas // 左右子树中存在一条即可
}
还可以使用如下中序遍历的方式实现：
// 使用树的中序遍历的方式
func hasPathSum(root *TreeNode, sum int) bool {
if(root == nil ) {
return false
}
var nodeStack []*TreeNode // 存放从根到当前节点所经过的节点
var sumStack []int // 存放从根节点到当前节点累积的和
var curNode *TreeNode = root // 当前节点
var curSum int // 当前节点累积的和
for(curNode != nil || len(sumStack) != 0) { // 当前节点不为空或者当前和所在栈不为空
for(curNode != nil) { // 节点不为空一直压栈
nodeStack = append(nodeStack, curNode) // 节点压栈
curSum += curNode.Val // 从根节点到当前节点累积和
sumStack = append(sumStack, curSum) // 当前和压栈
curNode = curNode.Left // 指向下一层左子树
}
// 节点为空，栈顶元素出栈
curNode = nodeStack[len(nodeStack)-1] // 栈顶节点出栈
nodeStack = nodeStack[:len(nodeStack)-1]
curSum = sumStack[len(sumStack)-1] // 栈顶累积和出栈
sumStack = sumStack[:len(sumStack)-1]
// 当前节点为叶子节点，并且到该节点所经过路径累积的和为sum，即满足条件返回
if(curSum == sum && curNode.Left == nil &&curNode.Right == nil){
return true
}
curNode = curNode.Right // 左子树没有满足条件的，再去右子树找是否有满足条件的
}
return false
}
leetcode 113. 路径总和 II
题目链接：https://leetcode-cn.com/problems/path-sum-ii/
题目描述给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
func pathSum(root *TreeNode, sum int) [][]int {
if root == nil {
return nil
}
var path []int
var res [][]int
dfsPathSum(root, sum, path, &res)
return res
}
// 深度优先遍历，注意这里传入的是resArr *[][]int
func dfsPathSum(curNode *TreeNode, target int, pathArr []int, resArr *[][]int) {
// 程序结束
if curNode == nil {
return
}
// 更新目标值，每放入一个节点，目标值应该相应减去对应节点的值，直到目标值为0
target -= curNode.Val
// 将当前遍历的节点放入路径集合
pathArr = append(pathArr, curNode.Val)
// 如果目标值减到了0 && 左节点为空 && 右节点为空 证明树已遍历完，此路径为目标路径
if curNode.Left == nil && curNode.Right == nil && target == 0 {
// 注意：这里重新使用append([]int{}, pathArr...)记录当前满足和为sum的一条路径，相当于对pathArr进行复制
// 如果直接使用*resArr = append(*resArr, pathArr)会造成部分结果不符合条件
*resArr = append(*resArr, append([]int{}, pathArr...))
}
// 递归左右子树
dfsPathSum(curNode.Left, target, pathArr, resArr)
dfsPathSum(curNode.Right, target, pathArr, resArr)
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）