网站首页二级下拉框怎么做,i18n wordpress,鞍山商城网站建设,怎么看网站是不是用凡客做的文章目录 中序遍历图解总结拓展#xff1a;回归与回溯 中序遍历图解 首先看下中序遍历的代码#xff0c;其接受一个根结点root作为参数#xff0c;判断根节点是否为nil#xff0c;不为nil则先递归遍历左子树。
func traversal(root *TreeNode,res *[]int) {if root nil … 文章目录 中序遍历图解总结拓展回归与回溯 中序遍历图解 首先看下中序遍历的代码其接受一个根结点root作为参数判断根节点是否为nil不为nil则先递归遍历左子树。
func traversal(root *TreeNode,res *[]int) {if root nil {return}traversal(root.Left,res)*res append(*res,root.Val)traversal(root.Right,res)
}我们把树根结点A传递给它其左结点为B右结点为C。
首先我们要检查root是否为nil其不为nil通过递归继续遍历左边的子树将左子树传递给递归函数该层递归函数的root为B其左子树为D 右子树为E判断root是否为nilroot不为nil继续将该树的左子树向下递归该层递归函数的root为D左右子树都为nil我们检查root是否为nilroot为D不为nil继续递归遍历D的左子树其左子树为nil所以该层递归函数的root为nil满足递归结束条件执行return退出该层递归函数。
递到此处时的运行栈如下图所示
此时的return会回到root为D的递归层D的左子树已经遍历完毕我们执行下一行语句append 该语句会将root的数据域加入到结构列表res中即访问到了D如下图
按照顺序继续执行接下来将使用递归遍历D的右子树这里D的右子树为nil所以我们传入的递归参数也为nil检测到root为nil我们退出该层递归函数回到调用层D该层的所有语句都执行完毕了。我们继续回到调用它的函数即B层的 traversal(root.Left,res)语句处 继续执行后序语句执行 *res append(*res,root.Val)记录root的数据域即访问B再执行下一条语句 递归访问B的右子树将E传递给它判断root是否为nilroot为E不为nil递归调用E的左子树左子树为nil判断root是否为nil为nil退出该层 执行下一行将E记录到结果中继续遍历E的右子树右子树为nil直接退出该层递归函数返回到了E的递归层E这层也执行完毕了返回到调用它的B层
随即B层也执行完了返回到调用它的A层 在该层执行下一行代码将A记录到结果中继续遍历A的右子树A的右子树为C其不为nil递归C的左子树FF不为nil递归F的左子树F的左子树为nil即传入的root为nil满足递归结束条件开始回归上层。
返回到调用它的F层将F记录到结果中。遍历F的右子树F的右子树也为nil退出该层到此F这层函数执行完毕返回到调用F的递归层 C下一行语句记录C
继续下一行语句递归C的右子树G判断该层递归的root是否为nil当前root为G不为nil递归G的左子树左子树为nil满足递归结束条件返回到调用它的G输出G递归G的右子树右子树为nil 满足递归结束条件返回到调用它的GG这层函数结束返回上层到C
C也运行完毕返回上层到AA也运行完毕此该树递归结束这样我们就得到了中序遍历序列
总结
再次回顾一下代码
func traversal(root *TreeNode,res *[]int) {if root nil {return}traversal(root.Left,res)*res append(*res,root.Val)traversal(root.Right,res)
}从我们的遍历全流程图解来看不难理解每个节点都是将其左子树全部递归遍历完后才开始遍历其右子树的如根节点A是将其左子树BDE全部遍历完后才开始遍历右子树的注意思考递归栈哦这样才能真正的理解。
中序遍历理解后前序和后续遍历是一样的道理。这时一起看下后续遍历的代码
func traversal(root *TreeNode,res *[]int) {if root nil {return}traversal(root.Left,res)traversal(root.Right,res)*res append(*res,root.Val)
}很多同学看到递归左右子树的那两行代码很容易陷入误区以为那两行是同时在执行认为遍历完root的左节点后立马遍历了其右节点这种理解是非常不对的实际是遍历完整个左子树后经过归回到当前层此时才会开始执行当前层的traversal(root.Right,res)语句去遍历右子树。 尤其是看到两条回溯语句写在同一行时会更容易误解如力扣104. 二叉树的最大深度
/*** definition for a binary tree node.* type treenode struct {* val int* left *treenode* right *treenode* }*/
func max (a, b int) int {if a b {return a}return b
}// 递归
func maxdepth(root *treenode) int {if root nil {return 0}return max(maxdepth(root.left), maxdepth(root.right)) 1
}实际最后一行代码是简化版等价于如下代码
/*** definition for a binary tree node.* type treenode struct {* val int* left *treenode* right *treenode* }*/
func max (a, b int) int {if a b {return a}return b
}// 递归
func maxdepth(root *treenode) int {if root nil {return 0}leftDepth : maxdepth(root.left) // 递归左子树的深度rightDepth : maxdepth(root.right) // 递归右子树的深度return max(leftDepth,rightDepth ) 1 // 当前根节点到叶子节点的最大深度
}此时再看此代码是不是好理解一些 它就是我们的后序遍历哇将左子树全部遍历完后才会开始遍历右子树最后则是根节点然后回到上层调用栈直到所有接地那遍历完毕递归函数执行完毕。
拓展回归与回溯
这里就是一个简介详细可见LeetCode 257. 二叉树的所有路径回溯详解
前序遍历以及回溯的过程如图 回溯和递归中回归的区别 回溯因为我们要把路径记录下来需要回溯来回退一个路径再进入另一个路径。 回归下层函数栈执行完成后回归到上层函数栈来 实际上回溯和回归都是伴随递归出现的只是回溯比回归多了一个路径回退的操作。
