参考文献 代码随想录
一、平衡二叉树
给定一个二叉树，判断它是否是
平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true
# 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 isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ if not root: return True ans = 0 def dfs(cur): if not cur: # 判断是否为空 return 0 a = dfs(cur.left) # 收先遍历左边的节点的节点差 if a == -1: # 如果是-1说明不是平衡 return -1 b = dfs(cur.right) if b == -1: return -1 ans = abs(a - b) if ans > 1: return -1 else: return 1 + max(a, b) return False if dfs(root) == -1 else True
二、二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
问题分析：要返回所有路径，那么你是不是便利到叶子节点的时候，就要收集结果了，那么，如何从当前的这节点去便利其它节点呢？使用回溯。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
迭代：
class Solution(object): def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ from collections import deque stack = deque() # 这个存放的是节点 depath = deque() # 这个存放的是对应的形式 ans = [] # 暂时存放每一个路径的结果 if root: # 如果不为空，入栈 stack.append(root) depath.append(str(root.val)) while stack: node = stack.pop() #出栈 d = depath.pop() # 中 if node and not node.left and not node.right: # 说明到了叶子节点，收集结果 ans.append(d) # 右 if node.right: stack.append(node.right) depath.append(d + '->' + str(node.right.val)) # 左 if node.left: stack.append(node.left) depath.append(d + '->' + str(node.left.val)) return ans
递归：
# 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 binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ if not root: return [] path = [] # 存放的是每一趟的路径 ans = [] # 存放的是最后的结果 def dfs(cur): if not cur: # 是否为空 return 0 path.append(cur.val) # 暂时存放每一条路径的值，为什么这个要写在下面这个if的前面呢?后面不行吗？不行，因为，如果你写在后面的话，假设当前节点就是叶子节点，那么你先判断它是否有左右节点，此时是没有的，而你确收集了结果，并没有加入也叶子节点 if not cur.left and not cur.right: # 到了叶子节点，收集结果 ans.append("->".join(map(str, path))) return if cur.left: # 便利左 dfs(cur.left) # path.pop() # 往后走，为什么要写在if里面，因为，你不可能只往后一步把 if cur.right: dfs(cur.right) path.pop() dfs(root) return ans
三、左叶子之和
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1] 输出: 0
问题分析：首先它是叶子节点，其次它是左孩子，然后我们是不是收集左右两边的左叶子节点，所以，当遍历到左节点的时候，判断它是否为左叶子节点，如果是，那么就把它的值赋值给左边的左叶子节点，然后在左边便利右边节点是否有左叶子节点，然后统计这个俩个的和
递归：
# 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 sumOfLeftLeaves(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 if not root.left and not root.right: # 左叶子说明有父亲 return 0 lefts = self.sumOfLeftLeaves(root.left) if root.left and not root.left.left and not root.left.right: lefts = root.left.val rights = self.sumOfLeftLeaves(root.right) s = lefts + rights return s
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
层次遍历：（迭代）
# 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 countNodes(self, root): """ :type root: TreeNode :rtype: int """ from collections import deque queen = deque() ans = [] if root: queen.append(root) while queen: count = len(queen) # 记录每层的个数 tmp = [] while count: node = queen.popleft() tmp.append(node) if node.left: queen.append(node.left) if node.right: queen.append(node.right) count -= 1 ans += tmp return len(ans)
递归：
# 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 countNodes(self, root): """ :type root: TreeNode :rtype: int """ ans = [] # 存放的是最后的结果 def dfs(cur): if not cur: # 是否为空 return 0 a = dfs(cur.left) # 先求左子树在求右子树之和 ，最后加上更节点 b = dfs(cur.right) return a + b + 1 return dfs(root)
