二叉树思考——一套模板解决所有遍历相关题

最近连续做了一些二叉树的遍历题，现在总结下规律

题目

在leetcode中

层次遍历1：给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
层次遍历2：给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
路径和1：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
路径和2：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

解析

其实这四道题，本质都是一个，就是遍历二叉树节点，只是3,4题在遍历的时候会需要记录值，所以只要做完第一题，其他题在这个基础上改一改即可！

层次遍历
例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题框架

如图

代码

按照解题步骤，如下代码

判空

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

定义数据结构

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        nodes=[root]
        res=[]

分析遍历的循环和跳出条件非常重要！！

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        nodes=[root]
        res=[]
        while nodes:  # 从上到下遍历
        	val=[]    # 记录遍历过的值
        	for i in range(len(nodes)):  #从左到右遍历一层
        	res.append(val) # 将记录完的值放入res中
         return res

完成循环，返回结果

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        nodes=[root]
        res=[]
        while nodes:
            val=[]
            for i in range(len(nodes)):
                node=nodes.pop(0)
                val.append(node.val)
                if node.left:
                    nodes.append(node.left)
                if node.right:
                    nodes.append(node.right)
            res.append(val)
        return res

拓展题目

2. 层次遍历2

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

只需要将遍历的结果res倒序输出即可

	return res[::-1]

3. 路径和1

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

示例: 
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路稍稍修改如下

  def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
           return False
        nodes=[(root,sum-root.val),]
        res=[]
        while nodes:
            node,cur_sum=nodes.pop(0)
            if not node.left and not node.right and cur_sum==0:
                return True
            if node.left:
                nodes.append((node.left,cur_sum-node.left.val))
            if node.right:
                nodes.append((node.right,cur_sum-node.right.val))
        return False

4. 路径和2

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
只需要

	nodes=[(root,[root.val])]

其中[root.val],表示当节点到达root时，路径为[root.val]，其他节点亦如此
同时，由于我们不再记录sum,（要记录也可以），所以我们最后直接比较路径和与sum的值相等作为正确条件

代码如下

    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
        res=[]
        if not root:
            return res
        nodes=[(root,[root.val]),]
        while nodes:
            node,tmp=nodes.pop(0)
            if not node.left and not node.right and sum(tmp)==sum_:
                res.append(tmp)
            if node.left:
                nodes.append((node.left,tmp+[node.left.val]))
            if node.right:
                nodes.append((node.right,tmp+[node.right.val]))
        return res