摘要

• 二叉树的深度是从根节点出发，到最远的叶节点的最长路径上的节点数
• 二叉树的高度是从最远叶节点出发，到根节点的最长路径上的节点数
• 完全二叉树可以的节点个数和树的高度与深度有明显的规律

LeetCode104 二叉树的深度

104. 二叉树的最大深度 - 力扣（Leetcode）

• 关键概念
  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
  • 从0开始为边的条数，从1开始为节点数
• 层序遍历实现求二叉树的深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.push(root);

        int res = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
            res++;
        }

        return res;
    }
};

• 后序遍历实现求二叉树的深度，
  • 实际上是逐步求每个节点的高度，从而最后求出根节点的高度。而根节点的高度正好是二叉树的深度。

class Solution {
public:
    int depthOf(TreeNode* node) {
        if (!node) return 0;
        int leftDepth = depthOf(node->left);
        int rightDepth = depthOf(node->right);
        int depth = 1 + max(leftDepth, rightDepth);
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return depthOf(root);
    }
};

LeetCode559 N叉树的最大深度

559. N 叉树的最大深度 - 力扣（Leetcode）

• 求树的深度，还是层序遍历更容易扩展到N叉树

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> que;
        if (root) que.push(root);

        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            for (int i = 0; i < size; i++) {
                for (auto& iter : que.front()->children) {
                    if (iter) que.push(iter);
                }
                que.pop();
            }
        }

        return depth;
    }
};

LeetCode111 二叉树的最小深度

111. 二叉树的最小深度 - 力扣（Leetcode）

• 二叉树的最小深度是根节点到最近叶节点的经过节点数。

  • 由于我们在递归终止条件中定义空节点的返回值为0（空节点对应一棵空的子树，高度或者深度自然是零）
  • 这会直接影响左右子树的最小深度比较。空节点并不是子树或者叶节点，所以需要我们手动排除空节点，只有左右子树都存在时比较左右子树的深度才有意义。

• 后序遍历的代码实现

class Solution {
public:
    int minDepthOf(TreeNode* node) {
        if (!node) {
            return 0;
        }
        int leftMinDepth = minDepthOf(node->left);
        int rightMinDepth = minDepthOf(node->right);
        int minDepth = 1;
        if (node->left && !node->right) minDepth += leftMinDepth;
        else if (!node->left && node->right) minDepth += rightMinDepth;
        else minDepth += min(leftMinDepth, rightMinDepth);
        return minDepth;
    }
    int minDepth(TreeNode* root) {
        return minDepthOf(root);
    }
};

• 层序遍历，在这道题中，层序遍历的代码依然更加直观、更加容易理解。

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.push(root);
        
        int res = 0;
        while (!que.empty()) {
            int size = que.size();
            res++;
            for (int i = 0; i < size; i++) {
                // 到达叶节点则直接返回当前深度
                if (!que.front()->left && !que.front()->right) {
                    return res;
                }
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
            
        }

        return res;
    }
};

LeetCode222 完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（Leetcode）

• 关键概念

  • 完美二叉树（Perfect Binary Tree），又称满二叉树（Full Binary Tree）：每层的节点数都达到最大值的二叉树就是完美二叉树。
    • 这里我再查阅了一下国外的教材，Full Binary Tree还有完满二叉树的意思，完满二叉树指的是如果一个节点有子节点，则该节点一定既有左孩子又有右孩子。和题目无关，只是定义上的歧义，这里先不讨论。
  • 完全二叉树（Complete Binary Tree），可以由完美二叉树定义，将完美二叉树按层序遍历的顺序，从最后一个节点向前逐个删除节点，得到的二叉树都是完全二叉树。
  • 完全二叉树（Complete Binary Tree）：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

• 利用完全二叉树的性质，可以减少计算完全二叉树的节点数需要访问的节点数。

  • 虽然完全二叉树的节点数和层数之间的关系是不确定的，但完全二叉树的子树可能包含完美二叉树。
  • 完美二叉树的节点个数和其层数是确定的，一个完美二叉树的层数为k，则该完美二叉树拥有的节点数为2^k - 1。

• 所以，虽然完全二叉树不一定是完美二叉树，但可以继续判断它的子树是否完美二叉树，如果它的子树是完美二叉树，就可以通过该子树的深度算出子树的节点数。这样就能达到减少访问的节点数的目的。

  • 递归函数的参数和返回值：判断当前子树是否为完美二叉树，如果为完美二叉树，则根据其深度计算节点个数，如果不为完美二叉树，则继续判断其左子树和右子树是否为完美二叉树。参数应为（子）树的根节点，返回值为节点数。
  • 递归的终止条件：一是当前子树的根节点为nullptr，空树返回值为0；而是当前子树为完美二叉树，计算出节点数后直接返回。
  • 单层递归的逻辑：从当前节点出发，计算当前树的左子树的深度和右子树的深度。若左子树的深度和右子树相等，则当前树为完美二叉树，可以直接根据深度计算出节点个数；若当前树不为完美二叉树，则递归判断其左子树和右子树是否为完美二叉树。

递归实现

class Solution {
public:
    int completeTreeNodes(TreeNode* node) {
        if (!node) return 0;
        TreeNode* left = node;
        int leftDepth = 0;
        while (left) {
            left = left->left;
            leftDepth++;
        }
        TreeNode* right = node;
        int rightDepth = 0;
        while (right) {
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return pow(2, leftDepth) - 1;
        }
        else {
            return completeTreeNodes(node->left) + completeTreeNodes(node->right) + 1;
        }
    }
    int countNodes(TreeNode* root) {
        return completeTreeNodes(root);
    }
};

普通的后序遍历

int postorderCountNodes(TreeNode* node) {
        if (!node) return 0;
        return postorderCountNodes(node->left) + postorderCountNodes(node->right) + 1; 
    }