算法练习Day16 （Leetcode/Python-二叉树）

递归何时需要返回值

1）搜索一整棵树且不需要处理递归返回值，就不需要返回值

2）需要搜索一整棵树且需要处理递归返回值，则需要返回

3）搜索其中一条符合条件的路径，就需要返回值，以便在遇到合适的路径时返回。

112. Path Sum

Given the?root?of a binary tree and an integer?targetSum, return?true?if the tree has a?root-to-leaf?path such that adding up all the values along the path equals?targetSum.

A?leaf?is a node with no children.

思路一：

使用递归法。使用DFS深度优先，尝试探索一条路径直达一个叶子节点，如果该路径不满足要求，则回溯以探索其他路径。

注意：这里用递减的方式记录该路径的节点值的sum直到减为0使得代码更加简洁。注意递归代码里是在input时就算好了当前路径（包含当前节点的子节点）的sum值，进入递归代码后先判断sum是否符合要求。如果不符合，跳出递归后把当前节点的子节点减去，然后再探索下一个子节点。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def traversal(self, cur, count):

        # reach the leave node and achieve the targetSum, return True  
        if not cur.left and not cur.right and count == 0:
            return True
        if not cur.left and not cur.right:
            return False
        
        if cur.left:
            count -= cur.left.val
            if self.traversal(cur.left, count):
                return True
            count += cur.left.val # backtrack
            # 如果当前的子节点加上后未出现满足要求的路径，就减去当前子节点的值，回归原状以探索下一个路径。
        if cur.right:
            count -= cur.right.val
            if self.traversal(cur.right, count):
                return True
            count += cur.right.val # backtrack

        return False 



    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False
        return  self.traversal(root, targetSum-root.val) # 记得减去root的值啊！！！

这种递归写法把当前路径的sum作为递归函数的input，隐式地实现了回溯。写法更加简洁。

class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False
        if not root.left and not root.right and targetSum == root.val:
            return True
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

思路二：迭代法。 这也是DFS。

相较于递归法，迭代法通常在内存上更有效率，因为递归会在调用栈上增加额外的内存负担。有时语言或环境优化不够的情况下，迭代会更有效率。迭代法代码可能更容易理解。

递归法则是代码更为简洁。有时也更利于维护。

class Solution(object):
    # Iteration
    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False
        st = [(root, root.val)]
        while st:
            node, path_sum = st.pop()

            if not node.left and not node.right and path_sum == targetSum:
                return True
            if node.right:
                st.append((node.right, path_sum+node.right.val))
            if node.left:
                st.append((node.left, path_sum+node.left.val))
        return False

相比上一道题，这里需要把所有满足要求的path记录并输出。所以就不用在traversal中提前return，而是再出现满足要求的path后，加入result。并且由于要记录所有的path，要记得回溯的时候pop出刚加进来的叶节点。

class Solution(object):
    def __init__(self):
        self.result = []
        self.path = []
        

    def traversal(self, cur, count):
        if not cur.left and not cur.right and count == 0:
            self.result.append(self.path[:])
            return 
        if not cur.left and not cur.right:
            return False

        if cur.left: # left
            count -= cur.left.val
            self.path.append(cur.left.val)
            self.traversal(cur.left, count)
            count += cur.left.val 
            self.path.pop()

        if cur.right: # right
            count -= cur.right.val
            self.path.append(cur.right.val)
            self.traversal(cur.right, count)
            count += cur.right.val 
            self.path.pop()
            
        return 


    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: List[List[int]]
        """
        self.result = []
        self.path = []
        if not root:
            return self.result
        self.path.append(root.val)
        self.traversal(root, targetSum-root.val)
        return self.result

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        if not root:
            return []
        stack = [(root, [root.val])]
        res = []
        while stack:
            node, path = stack.pop()
            if not node.left and not node.right and sum(path) == targetSum:
                res.append(path)
            if node.right:
                stack.append((node.right, path + [node.right.val]))
            if node.left:
                stack.append((node.left, path + [node.left.val]))
        return res

404. Sum of Left Leaves

Given the?root?of a binary tree, return?the sum of all left leaves.

A?leaf?is a node with no children. A?left leaf?is a leaf that is the left child of another node.

思路：首先明确什么是左叶子节点。即该节点无左右子节点，且是父节点的左节点。右子节点可能有它的左叶子节点，左子节点也可能有它的左叶子节点。注意，要通过父节点来判断是否是左叶子节点。

递归三要素：1） 递归函数参数和返回值：root和数值之和

2）终止条件：

if root is None: return 0;
if root.left is None && root.right is None: return 0;

3) 单层递归的逻辑：

遇到左叶子节点的时候，记下数值。通过递归法求左子树左叶子之和和右子树左叶子之和，相加起来就是整个树的左叶子之和。

递归法：

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if not root.left and not root.right:
            return 0
        
        leftValue  = self.sumOfLeftLeaves(root.left) # left 
        if root.left and not root.left.left and not root.left.right: #The left node is a left leave. 
            leftValue = root.left.val
        rightValue = self.sumOfLeftLeaves(root.right) # right 

        sum_val = leftValue + rightValue # middle 
        return sum_val 

递归法简化版：

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        leftValue = 0
        if root.left is not None and root.left.left is None and root.left.right is None:
            leftValue = root.left.val
        return leftValue + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

迭代法：

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        st = [root]
        result = 0
        while st:
            node = st.pop()
            if node.left and node.left.left is None and node.left.right is None:
                result += node.left.val
            if node.right:
                st.append(node.right)
            if node.left:
                st.append(node.left)
        return result 

Reference：

代码随想录