222. Count Complete Tree Nodes

    xiaoxiao2025-02-11  18

    Given a complete binary tree, count the number of nodes.

    Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

    1.先向最左和最右走,看是否是满二叉树;如果是可以直接算法节点数目;

    2.否则,对根的左右节点递归上述过程。

    /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int countNodes(TreeNode* root) { int hl = 0, hr = 0; TreeNode* l = root, *r = root; while (l){ l = l->left; hl++; } while (r){ r = r->right; hr++; } if (hl == hr) return (1 << hl) - 1; else{ return 1 + countNodes(root->left) + countNodes(root->right); } } };

    转载请注明原文地址: https://ju.6miu.com/read-1296315.html
    最新回复(0)