水头网站建设,网站群建设系统,网站界面设计的相关指南,开发一个网站需要多少钱跟着carl学算法#xff0c;本系列博客仅做个人记录#xff0c;建议大家都去看carl本人的博客#xff0c;写的真的很好的#xff01; 代码随想录 LeetCode#xff1a;222.完全二叉树节点的数量 给你一棵 完全二叉树 的根节点 root #xff0c;求出该树的节点个数。 完全二… 跟着carl学算法本系列博客仅做个人记录建议大家都去看carl本人的博客写的真的很好的 代码随想录 LeetCode222.完全二叉树节点的数量 给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。 完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层从第 0 层开始则该层包含 1~ 2h 个节点。 示例 1 输入root [1,2,3,4,5,6] 输出6 示例 2 输入root [] 输出0 示例 3 输入root [1] 输出1
类似后序遍历直接递归 public int countNodes(TreeNode root) {if (root null)return 0;int leftCount countNodes(root.left);int rightCount countNodes(root.right);return 1 leftCount rightCount;}利用完全二叉树的特性通过公式来计算 public int countNodes(TreeNode root) {if (root null)return 0;TreeNode leftNode root.left;int leftDepth 0;while (leftNode ! null) {leftNode leftNode.left;leftDepth;}TreeNode rightNode root.right;int rightDepth 0;while (rightNode ! null) {rightNode rightNode.right;rightDepth;}// 如果左右子树高度相同即时一颗完全二叉树可以使用公式来计算节点个数if (leftDepth rightDepth)return (2 leftDepth) - 1;int leftCount countNodes(root.left);int rightCount countNodes(root.right);return 1 leftCount rightCount;}
