LeetCode589/590/429/797-N叉树前/后序遍历、层序遍历、所有可能的路径
589.N叉树的前序遍历
整体逻辑与二叉树的前序遍历一致,但在访问子节点的时候需要用for循环进行递归调用,注意可以使用临时变量加冒号要要遍历访问的对象,这种特殊写法。
590.N叉树的后续遍历
同理,注意N叉树失去了中序遍历的写法。
429.N叉树的层序遍历
依旧是在访问子节点的时候,用for循环进行循环遍历,把所有分支的子节点都push进队列中,其他与二叉树遍历无逻辑结构上的不同。
797.所有可能的路径
由于图结构不包含环,所以不需要visited或onpath数组记录进行剪枝或者标记已访问的节点来避免死循环。
故而直接采用DFS遍历图。一共需要定义两个动态数组,一个二维动态数组用来返回最终的所有路径,一个一维动态数组用来记录当前的路径,一旦找到目标节点,就将当前记录的路径加入二维数组中,形成一次结果。
两个数组可以定义在函数内部作为局部变量,每次都将其引用传给traverse函数,而traverse每一次递归都将调用一次该引用值。也可以将两个数组定义在private私有位置,就不用给函数传参了,直接在traverse函数内部又可以直接调用与修改。
其中在前序位置,先把当前节点push到路径数组中,在后序位置把该节点移出路径数组,以实现实时更新当前DFS的路径。
判断是否抵达目标节点,也应当放在前序位置。在if语句内部,先将路径数组push进结果数组,还要把当前节点pop出路径数组,因为一旦判断抵达目标节点,就会马上return到上一个节点,跳过该目标节点后序位置的pop,这里极易出错。









