首页 计算机科学 算法 LeetCode

# 完全二叉树的节点个数

题目链接🔗

# 普通二叉树思路

# 递归

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

# 迭代

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int count = 0;
        while(!que.empty()) {
            int size = que.size();
            count += size;
            for(int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return count;
    }
};

# 完全二叉树思路

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第hh 层，则该层包含12h−11 ~ 2^{h-1} 个节点。

完全二叉树只有两种情况：

  1. 满二叉树
    • 可以直接用2TreeDepth−12^{TreeDepth} - 1 来计算。根节点深度为 1
  2. 最后一层叶子节点没有满
    • 分别递归左右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后按照情况 1 来计算。

那如何判断左子树或者右子树是满二叉树？

在完全二叉树中，如果递归向左遍历的深度等于递归向右的深度，就是满二叉树。

那本题可以利用这个公式来计算满二叉树的节点数量，如果不是满二叉树则递归。

class Soulution {
public：
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 0, rightDepth = 0;
        while(left) {
            left = left->left;
            leftDepth++;
        }
        while(right) {
            right = right->right;
            rightDepth++;
        }
        if(leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;    // 注意 (2<<1) 相当于 2^2，所以 leftDepth 初始为 0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

# 平衡二叉树

题目链接🔗

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。

  1. 确定递归函数的参数和返回值
  • 参数：当前传入的节点
  • 返回值： 以当前传入节点为根节点树的高度

如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。

所以如果已经不是二叉平衡树了，可以返回 - 1 来标记已经不符合平衡树的规则了。

  1. 明确终止条件

递归的过程中依然是遇到空节点了为终止，返回 0，表示当前节点为根节点的树高度为 0

  1. 确定单层递归逻辑

分别求出其左右子树的高度，如果差值小于等于 1，则返回当前二叉树的高度，否则返回 - 1，表示已经不是二叉平衡树了。

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回 - 1
    int getHeight(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

# 二叉树的所有路径

题目链接🔗

题目要求从根节点到叶子节点的路径，所以要前序遍历

因为我们要把路径记录下来，还需要回溯来回退一个路径再进入另一个路径。

二叉树所有路径

  1. 递归函数的参数和返回值

要传入根节点，记录每一条路径的 path，和存放结果集的 result，这里递归不需要返回值。

  1. 确定递归终止条件

当 cur 不为空，其左右孩子都为空的时候，就找到叶子节点

  1. 确定单层递归逻辑

因为是前序遍历要先处理中间节点。将中间节点放进 path 中，然后是递归和回溯的过程。

class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        // 叶子节点
        if (cur->left == nullptr && cur->right == nullptr) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == nullptr) return result;
        traversal(root, path, result);
        return result;
    }
};
注意在函数定义的时候 void traversal(TreeNode* cur, string path, vector<string>& result) ，定义的是 string path ，每次都是复制赋值，不用使用引用，否则就无法做到回溯的效果。
回溯就隐藏在 traversal(cur->left, path + "->", result); 中的 path + "->" ，因为并没有改变 path 的数值，执行完递归函数之后，path 依然是之前的数值（相当于回溯了）。
# 左子叶之和
题目链接🔗
左叶子的定义：节点 A 的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么 A 节点的左孩子为左叶子节点。
要注意是判断左叶子，不是二叉树左侧节点，所以不能层序遍历。
那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。
# 递归
  1. 确定递归函数的参数和返回值
判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和。
  1. 确定终止条件
如果是空节点则左子叶值为 0.
并且，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点，那其左叶子也必定是 0。
  1. 确定单层递归逻辑
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right== nullptr) return 0;
        int leftValue = sumOfLeftLeaves(root->left);    // 左
        if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);  // 右
        int sum = leftValue + rightValue;               // 中
        return sum;
    }
};
/* 精简代码 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftValue = 0;
        if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {
            leftValue = root->left->val;
        }
        return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};
# 迭代
迭代前中后序都可以，以前序为例。
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return 0;
        st.push(root);
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
                result += node->left->val;
            }
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return result;
    }
};