目录
LeetCode110. 平衡二叉树
1. 思路
平衡二叉树的概念：每个节点的左子树和右子树的高度差的绝对值不超过1
这里又涉及到高度和深度的概念了
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数；
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数；
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题）；
因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。
回到本题
此时大家应该明白了既然要求比较高度，必然是要后序遍历。
递归三步曲分析：
- 明确递归函数的参数和返回值
参数：当前传入节点。返回值：以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了；所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if self.get_height(root) != -1:
return True
else:
return False
def get_height(self, root: TreeNode) -> int:
- 明确终止条件
递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0。
# Base Case
if not root: return 0
- 明确单层递归的逻辑
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值；分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉平衡树了。
leftHeight = self.get_height(node.left) # 左
rightHeight = self.get_height(node.right) #右
if leftHeight == -1 or rightHeight == -1: return -1
elif abs(leftHeight-rightHeight)>1: return -1 # 中
else: return 1+max(leftHeight,rightHeight)
2. 代码实现
# 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
#########################################2022.10.9
# 后序递归解法
# time:O(N);space:O(height)
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
result = self.getHeight(root)
return False if result == -1 else True
def getHeight(self,node):
# base case
if node == None: return 0
# 中序
# 左
leftHeight = self.getHeight(node.left)
if leftHeight == -1: return -1
# 右
rightHeight = self.getHeight(node.right)
if rightHeight == -1: return -1
# 中
if abs(leftHeight-rightHeight)>1: return -1
else: return (max(leftHeight,rightHeight)+1)
3. 复杂度分析
时间复杂度：O(N)
N 为二叉树的节点个数，使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)；
空间复杂度：O(N)
其中 n 是二叉树中的节点个数，空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。
4. 思考
本题也可以用迭代的方式解决（二刷再看）
在**104.二叉树的最大深度 (opens new window)**中我们可以使用层序遍历来求深度，但是就不能直接用层序遍历来求高度了，这就体现出求高度和求深度的不同。
本题的迭代方式可以先定义一个函数，专门用来求高度。
这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度）
然后再用栈来模拟后序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合，代码如下：
class Solution: def isBalanced(self, root: TreeNode) -> bool: st = [] if not root: return True st.append(root) while st: node = st.pop() #中 if abs(self.getDepth(node.left) - self.getDepth(node.right)) > 1: return False if node.right: st.append(node.right) #右（空节点不入栈） if node.left: st.append(node.left) #左（空节点不入栈） return True def getDepth(self, cur): st = [] if cur: st.append(cur) depth = 0 result = 0 while st: node = st.pop() if node: st.append(node) #中 st.append(None) depth += 1 if node.right: st.append(node.right) #右 if node.left: st.append(node.left) #左 else: node = st.pop() depth -= 1 result = max(result, depth) return result当然此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。
虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。**例如：都知道回溯法其实就是递归，但是很少人用迭代的方式去实现回溯算法！**因为对于回溯算法已经是非常复杂的递归了，如果在用迭代的话，就是自己给自己找麻烦，效率也并不一定高。
通过本题可以了解求二叉树深度 和 二叉树高度 的差异，求深度适合用前序遍历，而求高度适合用后序遍历。
Reference：
本题学习时间： 60分钟。
LeetCode257. 二叉树的所有路径
链接： 257. 二叉树的所有路径 - 力扣（LeetCode）
1. 思路
这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一一个路径在进入另一个路径。
前序遍历以及回溯的过程如图：（其遍历顺序按照每一条线上的标号从小到大遍历）
我们先使用递归的方式，来做前序遍历。要知道递归和回溯是相辅相成的，本题也需要回溯。
2. 代码实现
递归三部曲
递归函数函数参数以及返回值
要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值，代码如下：
class Solution: def binaryTreePaths(self, root): path = '' result = [] if not root: return result self.traversal(root, path, result) return result def traversal(self, cur, path, result:):确定递归终止条件
再写递归的时候都习惯了这么写：
if (cur == None) {终止处理逻辑}但是本题的终止条件这样写会很麻烦，因为本题要找到叶子节点，就开始结束的处理逻辑了（把路径放进result里）。
本题的终止条件应该怎么写？
那么什么时候算是找到了叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点；所以本题的终止条件是：
# 若当前节点为leave，直接输出 if not cur.left and not cur.right: # 终止处理逻辑为什么没有判断cur是否为空呢？
因为下面的单层递归处理逻辑可以控制空节点不入循环。
再来看一下终止处理的逻辑
这里使用数组结构path来记录路径，所以要把数组 结构的path转为string格式，在把这个string 放进 result里。
那么为什么使用了数组 结构来记录路径呢？ 因为在下面处理单层递归逻辑的时候，要做回溯，使用 数组结构方便来做回溯。
可能有的同学问了，**我看有些人的代码也没有回溯啊？**其实是有回溯的，只不过隐藏在函数调用时的参数赋值里，下文我还会提到。这里我们先使用数组结构的path容器来记录路径，那么终止处理逻辑如下：
if not cur.left and not cur.right: sPath = "" for i in range(0,len(path)-1): sPath += str(path[i]) sPath += "->" # 因为最后一个元素的后面不需要带箭头所以要单独处理 sPath += str(path[len(path)-1]) result.append(sPath) return确定单层递归逻辑
前序遍历的中左右处理逻辑
因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中，
path.append(cur.val);这里有个细节是中节点的处理必须放在终止条件的前面，因为判断到叶子节点就会终止，就会漏掉叶子节点，所以必须放在他之前。
然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了；所以递归前要加上判断语句，下面要递归的节点是否为空，如下：
if cur.left: traversal(cur.left,path,result) if cur.right: traversal(cur.right,path,result)回溯过程
此时还没完，递归完，要做回溯啊，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。那么回溯要怎么回溯呢，一些同学会这么写，如下：
# 回溯错误写法 if cur.left: traversal(cur.left,path,result) if cur.right: traversal(cur.right,path,result) path.pop()这个回溯就要很大的问题，我们知道，回溯和递归是一一对应的，有一个递归，就要有一个回溯，这么写的话相当于把递归和回溯拆开了， 一个在花括号里，一个在花括号外。**所以回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！**那么代码应该这么写：
# 回溯的正确写法 if cur.left: traversal(cur.left,path,result) path.pop() # 回溯 if cur.right: traversal(cur.right,path,result) path.pop() # 回溯
本题整体代码如下：
# 二叉树的所有路径 递归回溯
# 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]
"""
path = []
result = []
if root == None: return result
self.traversal(root,path,result)
return result
def traversal(self,node,path,result):
path.append(node.val) # 中
# base case
if node.left == None and node.right == None:
sPath = ""
size = len(path)
for i in range(0,size-1):
sPath += str(path[i])
sPath += str("->")
sPath += str(path[size-1])
result.append(sPath)
return
if node.left:
self.traversal(node.left,path,result)
path.pop()
if node.right:
self.traversal(node.right,path,result)
path.pop()
3. 复杂度分析
时间复杂度：O(N) / O(N^2) 其中 N 表示节点数目，每个节点会被访问一次且只会被访问一次，每一次会对将节点加入path数组里，然后添加到sPath 里，再添加到result里，这些操作在Python中都是O(1)级别的，因此时间代价为 O(N)，故时间复杂度为 O(N)；
如果path.append的操作是O（N）的话，数组长度固定，每次append都要拷贝一次的话，整个时间复杂度变为O(N^2)；
空间复杂度：O(N^2) / O(logN * logN)
4. 思考
上述的代码清晰地体现了每一步的思路和体现了回溯，可以精简成如下的代码：（二刷再看）
# 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): path = '' result = [] if not root: return result self.traversal(root, path, result) return result def traversal(self, cur, path, result): path += str(cur.val) # 若当前节点为leave，直接输出 if not cur.left and not cur.right: result.append(path) if cur.left: # + '->' 是隐藏回溯 self.traversal(cur.left, path + '->', result) if cur.right: self.traversal(cur.right, path + '->', result)- 迭代写法（二刷再看）
至于非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程，这里除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径，其中stack是前序遍历节点的栈，path_st是对应stack中的节点的路径；
from collections import deque
class Solution:
"""二叉树的所有路径 迭代法"""
def binaryTreePaths(self, root: TreeNode) -> List[str]:
# 题目中节点数至少为1
stack, path_st, result = deque([root]), deque(), []
path_st.append(str(root.val))
while stack:
cur = stack.pop()
path = path_st.pop()
# 如果当前节点为叶子节点，添加路径到结果中
if not (cur.left or cur.right):
result.append(path)
if cur.right:
stack.append(cur.right)
path_st.append(path + '->' + str(cur.right.val))
if cur.left:
stack.append(cur.left)
path_st.append(path + '->' + str(cur.left.val))
return result
3. 本文我们开始初步涉及到了回溯，很多同学过了这道题目，可能都不知道自己其实使用了回溯，回溯和递归都是相伴相生的。
Reference：
本篇学习时间：60分钟。
LeetCode404. 左叶子之和
1. 思路
理解到底什么是左叶子？
首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历；因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点；
Example：
大家思考一下左图中二叉树，左叶子之和究竟是多少？**其实是0，因为这棵树根本没有左叶子！**但看右图的左叶子之和是多少？
相信通过这两个图，大家可以最左叶子的定义有明确理解了。
那么**判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子；**如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。
遍历顺序是啥？
递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和；
2. 代码实现
递归三部曲：
确定递归函数的参数和返回值
判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int；使用题目中给出的函数就可以了。
确定终止条件
如果遍历到空节点，那么左叶子值一定是0
注意，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点，那其左叶子也必定是0，那么终止条件为：
if node == None: return 0 # 其实这个也可以不写，如果不写不影响结果，但就会让递归多进行了一层 # 但是建议该返回时就返回，不做无用的递归 if node.left == None and node.right == None: return 0确定单层递归的逻辑
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和
left_left_leaves_sum = self.sumOfLeftLeaves(root.left) # 左 right_left_leaves_sum = self.sumOfLeftLeaves(root.right) # 右 cur_left_leaf_val = 0 if root.left and not root.left.left and not root.left.right: cur_left_leaf_val = root.left.val totalValue = cur_left_leaf_val + left_left_leaves_sum + right_left_leaves_sum # 中 return totalValue
整体递归代码如下：
# 后序递归遍历
# time:O(N);space:O(N)
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# base case
# 空节点的左叶子之和为0
if root == None: return 0
# 叶子节点的左叶子之和为0
if root.left == None and root.right == None: return 0
# 左
leftValue = self.sumOfLeftLeaves(root.left)
# 右
rightValue = self.sumOfLeftLeaves(root.right)
# 看看是否碰到了左叶子
# 这里需要先定义，因为如果没有进入下面的条件的话，在total那里加上会报错
leftLeafNodeValue = 0
if root.left and root.left.left == None and root.left.right == None:
leftLeafNodeValue = root.left.val
# 中
totalValue = leftValue + rightValue + leftLeafNodeValue
return totalValue
3. 复杂度分析
时间复杂度：O(n)
其中 n 是树中的节点个数。
空间复杂度：O(n)
空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为 O(n)，对应的空间复杂度也为 O(n)。
4. 思考
迭代做法，迭代法使用前中后序都是可以的，只要把左叶子节点统计出来，就可以了
# 迭代解法 # time：O(N)；space：O(N) class Solution(object): def sumOfLeftLeaves(self, root): """ :type root: TreeNode :rtype: int """ if root == None : return 0 stack = [root] result = 0 while stack: cur = stack.pop() if cur.left and cur.left.left == None and cur.left.right == None: result += cur.left.val if cur.left: stack.append(cur.left) if cur.right: stack.append(cur.right) return result这道题目要求左叶子之和，其实是比较绕的，因为不能判断本节点是不是左叶子节点。此时就要通过节点的父节点来判断其左孩子是不是左叶子了。**平时我们解二叉树的题目时，已经习惯了通过节点的左右孩子判断本节点的属性，而本题我们要通过节点的父节点判断本节点的属性。**希望通过这道题目，可以扩展大家对二叉树的解题思路。
Reference：代码随想录 (programmercarl.com)
本题学习时间：80分钟。
本篇学习时间大约三个多小时，总结字数9000+，平衡二叉树对深度和高度进一步理解；二叉树的所有路径初次接触了回溯，左叶子之和第一次用父节点判断本节点的属性，收获满满！（求推荐）