【中等】统计完全二叉树的节点数－Java

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree; import live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree.BinaryTreePrinter2.Node; /** * 统计完全二叉树的节点数 * * 【题目】 * 给定一棵完全二叉树的头节点head返回这棵树的节点个数。 * * 【要求】 * 如果完全二叉树的节点数为N请实现时间复杂度低于O(N)的解法。 * * 【难度】 * 中等 * * 【解答】 * 遍历整棵树当然可以求出节点数但这肯定不是最优解法本文不再详述。 * * 如果完全二叉树的层数为h本文的解法可以做到时间复杂度为O(h^2)具体过程如下 * 、如果headnull说明是空树直接返回。 * 、如果不是空树就求树的高度求法是找到树的最左节点看能到哪一层层数记为h。 * 、这一步是求解的主要逻辑也是一个递归过程记为bs(node,l,h)node表示当前节点l表示node所在的层数h表示整棵树的 * 层数是始终不变的。bs(node,l,h)的返回值表示以node为头的完全二叉树的节点数是多少。初始时node为头节点headl为因 * 为head在第层一共有h层始终不变。 * * 全部过程请参看如下代码中的nodeNum方法。 * * 每一层只会选择一个节点node进行bs的递归过程所以调用bs函数的次数为O(h)。每次调用bs函数时都会查看node右子树的最左 * 节点所以会遍历O(h)个节点整个过程的时间复杂度为O(h^2)。 * * author Created by LiveEveryDay */ public class DoStatisticsCompleteBinaryTreeNodeCount { public static int nodeNum(Node head) { if (head null) { return 0; } return bs(head, 1, mostLeftLevel(head, 1)); } public static int bs(Node node, int l, int h) { if (l h) { return 1; } if (mostLeftLevel(node.right, l 1) h) { return (1 (h - l)) bs(node.right, l 1, h); } else { return (1 (h - l - 1)) bs(node.left, l 1, h); } } public static int mostLeftLevel(Node node, int level) { while (node ! null) { level; node node.left; } return level - 1; } public static void main(String[] args) { Node node1 new Node(2); Node node2 new Node(3); Node node3 new Node(5); Node node4 new Node(7); Node node5 new Node(8); Node node6 new Node(1); Node node7 new Node(3); node1.left node2; node1.right node3; node2.left node4; node2.right node5; node3.left node6; node3.right node7; System.out.printf(The node count is: %d%n, nodeNum(node1)); } } // ------ Output ------ /* The node count is: 7 */