代码随想录算法训练营第十五天| 二叉树3

再一次涉及到，什么是高度，什么是深度，可以巩固一下。

题目链接/文章讲解/视频讲解：代码随想录

状态：要辨别新增函数的位置，self的用法

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数，从上往下数

二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数，从下往上数

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if self.get_height(root)==-1:
            return False
        else:
            return True
    def get_height(self,node):
        if not node:
            return 0
        if (leftlength:=self.get_height(node.left))==-1:
            return -1
        if (rightlength:=self.get_height(node.right))==-1:
            return -1
        if abs(rightlength-leftlength)>1:
            return -1
        else:
            return 1+max(rightlength,leftlength)

257. 二叉树的所有路径 （优先掌握递归）

这是大家第一次接触到回溯的过程， 我在视频里重点讲解了 本题为什么要有回溯，已经回溯的过程。

如果对回溯 似懂非懂，没关系， 可以先有个印象。

题目链接/文章讲解/视频讲解：代码随想录

状态：需要看讲解

栈，先进后出规则

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result=[]
        path=[]
        if not root:
            return result
        self.traveral(root,path,result)
        return result

    def traveral(self,cur,path,result):
        path.append(cur.val)
        if not cur.left and not cur.right:
            spath="->".join(map(str,path))
            result.append(spath)
            return
        if cur.left:
            self.traveral(cur.left,path,result)
            path.pop()
        if cur.right:
            self.traveral(cur.right,path,result)
            path.pop()

404.左叶子之和 （优先掌握递归）

其实本题有点文字游戏，搞清楚什么是左叶子，剩下的就是二叉树的基本操作。

题目链接/文章讲解/视频讲解：代码随想录

状态：知道递归思想，但是完整写出代码有难度

感觉下面这个代码比讲解代码更好理解，递归处理左子树和右子树的左叶子

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        total=0
        if root.left and not root.left.left and not root.left.right:
            total+=root.left.val
        total+=self.sumOfLeftLeaves(root.left)
        total+=self.sumOfLeftLeaves(root.right)
        return total

222.完全二叉树的节点个数（优先掌握递归）

需要了解，普通二叉树 怎么求，完全二叉树又怎么求

题目链接/文章讲解/视频讲解：代码随想录

状态：可以按类别写出递归，但在仅使用if还是if、elif配合使用的选择上存在问题，另外按if和elif写出来之后，可以精简逻辑

if和elif配合

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        count=0
        if root.left and not root.right:
            count=1+self.countNodes(root.left)
        elif not root.left and root.right:
            count=1+self.countNodes(root.right)
        else:
            count=1+self.countNodes(root.left)+self.countNodes(root.right)
        return count

精简递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1+self.countNodes(root.left)+self.countNodes(root.right)