代码随想录算法训练营第17天 |● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和

前言

迭代法，大家可以直接过，二刷有精力的时候 再去掌握迭代法。

110.平衡二叉树

思路

求高度，仍然是后序遍历
单层处理逻辑：如果左右高度差小于1的话，返回子节点最大高度+1；如果发现大于1了，就返回-1【这个是我自己思考没想到的，主要是-1也是需要一层一层往上返回的】

题外话：本题的迭代法比较复杂， 不一定非要写出来

方法一 递归法

注意事项

1. 本题一定是需要额外定义一个函数进行递归的，和昨天的题目不一样，原因在于题目需要返回的是true或者false，而判断是否为平衡需要返回的是高度，并且还需要返回-1来一路向上传播
2. 教程中💟使用了:= 是海象操作符（Walrus Operator），用于在表达式中进行变量赋值。
   例如if (x := 5) > 3: print(x)【但是只有python3能用】

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def getheight(root):
            if not root: return 0#到了叶子节点返回高度0
            left_height = getheight(root.left)
            right_height = getheight(root.right)
            #如果子节点都不是平衡的，那么-1一路往上传递
            if left_height == -1:
                return -1
            if right_height == -1:
                return -1
            if abs(left_height-right_height) > 1:
                return -1
            else:
                return max(left_height,right_height)+1

        if not root: return True
        result = getheight(root)
        return True if result>0 else False
#精简版
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self.get_hight(root) != -1
    def get_hight(self, node):
        if not node:
            return 0
        left = self.get_hight(node.left)
        right = self.get_hight(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return max(left, right) + 1 

257. 二叉树的所有路径

思路

前序遍历+回溯思想
递归三部曲

1. 找传入参数和传出：
   
2. 迭代终止条件：找到了叶子节点，也就是它的左右孩子为空，返回；发现这条路径到头了，还需要将这个时候path中存储的这一条变成字符串append到result里面
3. 单层逻辑：将这一层的节点放入path中；左右孩子进入递归；最后还要回溯：
   • 也就是中左右的遍历顺序：左边孩子走完了，需要popleft里面已经有的节点，然后再进入右孩子。

方法一 递归法

注意事项：

1. 使用->链接，并且还要转换为字符串，'->'.join(map(str,path))背住哈；或者使用教程里面第二种隐性回溯写法path += str(cur.val) 和传参path + '->'

# 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
from collections import deque
class Solution(object):
    def traversal(self,curr,path,result):
        if not curr: return
        #找到了叶子节点
        path.append(curr.val)
        if not curr.left and not curr.right:
            result.append('->'.join(map(str,path)))
            return
        if curr.left:
            self.traversal(curr.left,path,result)
            path.pop()
        if curr.right:
            self.traversal(curr.right,path,result)
            path.pop()



    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        result =[]
        path = []
        self.traversal(root,path,result)
        return result

隐性回溯法
使用slice[:]全面浅拷贝，这样我们后面处理的是复值之后的path，就不需要pop了

class Solution(object):
    def traversal(self,curr,path,result):
        if not curr: return
        #找到了叶子节点
        path.append(curr.val)
        if not curr.left and not curr.right:
            result.append('->'.join(map(str,path)))
            return
        if curr.left:
            self.traversal(curr.left,path[:],result)
            # path.popleft()
        if curr.right:
            self.traversal(curr.right,path[:],result)
            # path.popleft()



    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        result =[]
        path = []
        self.traversal(root,path,result)
        return result

方法二

404.左叶子之和

首先给出左叶子的定义：参考教程
节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

思路

后序遍历：计算当前节点的子节点的左叶子之和然后往上传
递归三部曲

1. 参数：返回的是int，传入的是root
2. 终止条件：如果左右孩子为空，那么到叶子节点了，返回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#到了叶子节点的情况
        left_sum,right_sum = 0,0
        if root.left:
            left_sum = self.sumOfLeftLeaves(root.left)
        if root.left and not root.left.left and not root.left.right:#如果左节点存在，但是左节点没有子节点，说明是左叶子
            left_sum = root.left.val
        if root.right:
            right_sum = self.sumOfLeftLeaves(root.right)
        
        return left_sum+right_sum
 简洁版本
 class Solution:
    def sumOfLeftLeaves(self, root):
        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)       

方法二 迭代法

总结

今天去看seventeen，看掉了睡觉和学习申论的时间，后悔啊。