222. 完全二叉树的节点个数
这道题如果要最快,就要充分利用完全二叉树的性质。甚至还有二分查找法,还没怎么认真看
利用树的深度判断是否为完全二叉树。若是,直接公式得出节点数。
class Solution { 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; else return countNodes(root->left)+countNodes(root->right)+1; } };
递归法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countNodes(TreeNode* root) { if(root==nullptr) return 0; if(root->left==nullptr&&root->right==nullptr) return 1; return countNodes(root->left)+countNodes(root->right)+1; } };
迭代法,我写的这个比递归法慢很多
class Solution { public: int countNodes(TreeNode* root) { if(root==nullptr) return 0; queue<TreeNode*> qqq; qqq.push(root); int res=0; while(!qqq.empty()) { int size=qqq.size(); for(int i=0;i<size;i++) { TreeNode *t=qqq.front(); qqq.pop(); res++; if(t->left) qqq.push(t->left); if(t->right) qqq.push(t->right); } } return res; } };
标签:right,TreeNode,leetcode222,int,nullptr,二叉树,root,节点,left From: https://www.cnblogs.com/uacs2024/p/16851050.html