代码随想录算法训练营Day16

二叉树深度:节点到根结点的距离. (每有一个节点 +1包含当前节点.) 越向下越大.

二叉树高度:节点到叶子节点的距离. (每有一个节点 +1包含当前节点.) 越向上越大.

求高度:后序遍历 左右中; 求深度: 前序遍历 中左右;

104. Maximum Depth of Binary Tree

求二叉树的最大深度,就是求最大高度. 把需要前序解决的问题,转换为后序的问题.

层序迭代 & 后序递归

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:# Sol1: 层序遍历# depth = 0# if not root: return depth# q = [root]# while q:#     depth += 1#     for _ in range(len(q)):#         cur = q.pop(0)#         if not cur: continue #         if cur.left: q.append(cur.left)#         if cur.right: q.append(cur.right)# return depth# Sol2: 后序 递归if not root: return 0return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

这里展现一下,前序递归的回溯思想(重点关注,相较于上面的后序遍历,麻烦在哪里.)

class solution {
public:int result;void getdepth(treenode* node, int depth) {result = depth > result ? depth : result; // 中if (node->left == NULL && node->right == NULL) return ;if (node->left) { // 左depth++;    // 深度+1getdepth(node->left, depth);depth--;    // 回溯，深度-1}if (node->right) { // 右depth++;    // 深度+1getdepth(node->right, depth);depth--;    // 回溯，深度-1}return ;}int maxdepth(treenode* root) {result = 0;if (root == NULL) return result;getdepth(root, 1);return result;}
};

代码简化后:

class solution {
public:int result;void getdepth(treenode* node, int depth) {result = depth > result ? depth : result; // 中if (node->left == NULL && node->right == NULL) return ;if (node->left) { // 左getdepth(node->left, depth + 1);}if (node->right) { // 右getdepth(node->right, depth + 1);}return ;}int maxdepth(treenode* root) {result = 0;if (root == 0) return result;getdepth(root, 1);return result;}
};

559. Maximum Depth of N-ary Tree

两种方法: 层序 迭代 & 前序深度搜索 递归.

class Solution:def maxDepth(self, root: 'Node') -> int:# Sol1 解题同Leetcode104 层序 迭代# depth = 0# q = [root]# if not root: return depth# while q:#     depth += 1#     for i in range(len(q)):#         cur = q.pop(0)#         if not cur: continue#         for cc in cur.children:#             if cc: q.append(cc)# return depth# # SC: 其在最坏情况下会达到 O(n)# # TC: O(n)# Sol2 深度优先 后序 递归depth = 0if not root: return depthfor cc in root.children:depth = max(depth, self.maxDepth(cc))return depth+1

111. Minimum Depth of Binary Tree

这里也是用后序递归遍历, (求深度)

后序递归 & 前序递归 都需关注五种情况: 1) 左有右空, 2) 左空右有, 3) 左右皆空, 4) 左右非空, 5) 根节点空

重复: 递归三要素: 递归函数input, output; 递归终止条件; 每一层递归的处理

class Solution:def minDepth(self, root: Optional[TreeNode]) -> int:# Sol1 后序递归: 分开处理左子树为空,右子树为空的情形# if not root: return 0# if root.left and (not root.right): return self.minDepth(root.left) + 1# if root.right and (not root.left): return self.minDepth(root.right) + 1# return min(self.minDepth(root.left), self.minDepth(root.right)) + 1# Sol2 这是前序! 回溯求深度def getDepth(root: TreeNode, depth: int) -> int:if not (root.left or root.right): return min(res, depth)if root.left and (not root.right): return getDepth(root.left, depth + 1)if root.right and (not root.left): return getDepth(root.right, depth + 1)if root.left and root.right: return min(getDepth(root.right, depth + 1), getDepth(root.left, depth + 1))if not root: return 0res = float("inf")return getDepth(root, 1)# Sol3 迭代# 层序遍历# if not root: return 0# q = [root]# depth = 0# while q:#     depth += 1#     for _ in range(len(q)):#         cur = q.pop(0)#         if cur.left: q.append(cur.left)#         if cur.right: q.append(cur.right)#         if not (cur.left or cur.right):#             return depth

222. Count Complete Tree Nodes

对于一个普通问题,计算node数量的深度优先递归算法为:

def countNodes(self, root: TreeNode)-> int:if not root: return 0return self.countNodes(root.left) + countNodes(root.right) + 1

• 时间复杂度为O(n), 空间复杂度为O(1)(不考虑递归调用栈)(考虑系统递归调用栈, 则空间复杂度为O(log n).

但这是一个普适的解法, 对于此题给的完全二叉树的特点没有利用起来, 进一步考虑如何使用完全二叉树的特点更快解出此题.

首先需要明确完全二叉树的定义: 它是一棵空树**或者它的叶子节点只出在最后两层, 若最后一层不满则叶子节点只在最左侧. **

!!! 完全二叉树的左右子树一定也是完全二叉树.

在完全二叉树中, 如果递归向左遍历的深度等于递归向右遍历的深度, 那说明就是满二叉树.

判断其子树岂不是满二叉树, 如果是则利用用公式计算这个子树（满二叉树）的节点数量, 如果不是则继续递归.

class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:# 首先需要明确完全二叉树的定义: 它是一棵空树或者它的叶子节点只出在最后两层, 若最后一层不满则叶子节点只在最左侧.# 在完全二叉树中, 如果递归向左遍历的深度等于递归向右遍历的深度, 那说明就是满二叉树.# 判断其子树岂不是满二叉树, 如果是则利用用公式计算这个子树（满二叉树）的节点数量, 如果不是则继续递归.# Sol1 递归if not root: return 0 # 终止条件1leftDep, rightDep = 0, 0cur0 = rootwhile cur0:leftDep += 1cur0 = cur0.leftcur = rootwhile cur:rightDep += 1cur = cur.rightif leftDep == rightDep: # 终止条件2return 2 ** leftDep - 1else:return 1 + self.countNodes(root.left) + self.countNodes(root.right) # 这里其实是 后序遍历

• 时间复杂度：O(logN∗logN)O(log N * log N)O(logN∗logN)，其中 n 是完全二叉树的节点数。(最差为O(N)O(N)O(N))
  首先需要 O(h) 的时间得到完全二叉树的最大层数，其中 h 是完全二叉树的最大层数。
  使用二分查找确定节点个数时，需要查找的次数为 O(log2h)=O(h)O(log 2^h)=O(h)O(log2h)=O(h)，每次查找需要遍历从根节点开始的一条长度为 hh 的路径，需要$ O(h)$ 的时间，因此二分查找的总时间复杂度是 O(h2)O(h^2)O(h2)。
  因此总时间复杂度是 O(h2)O(h^2)O(h2)。由于完全二叉树满足 2h≤n<2h+12^h \le n < 2^{h+1}2h≤n<2h+1，因此有$ O(h)=O(log n)，，，O(h ^2 )=O(log^2 n)$。
• 空间复杂度：O(1)O(1)O(1)