树的深度相关问题

无意刷到这几道题，既然都看到了，哪有不做的道理

首先说明，本文采用的例子均为

        1
       / \
      2   3
     / \ / \
    4  5 6  7
   / \
  8   9

结点定义为

struct Node {
    int value;
    Node* left = nullptr;
    Node* right = nullptr;
};

树的深度

这个问题很简单了吧，基本的数据结构

最简单的就是递归，将左枝和右枝的深度取最大加一就好

/**
 * expect 4
 */
int get_tree_depth(Node* root) {
    if (!root) {
        return 0;
    }
    int left_depth = get_tree_depth(root->left);
    int right_depth = get_tree_depth(root->right);
    return max(left_depth, right_depth) + 1;
}

所有子树的深度之和

这个实际上也很简单，先获取当前结点的深度，然后递归求取左右子结点的所有子树的深度之和，然后将结果相加就好

/**
 * expect 16
 */
int get_all_depth(Node* root) {
    if (!root) {
        return 0;
    }
    int root_depth = get_tree_depth(root);
    int left_depth = get_all_depth(root->left);
    int right_depth = get_all_depth(root->right);
    return root_depth + left_depth + right_depth;
}

未完...