分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter
package live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree; import live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree.BinaryTreePrinter2.Node; /** * 统计完全二叉树的节点数 * * 【题目】 * 给定一棵完全二叉树的头节点head，返回这棵树的节点个数。 * * 【要求】 * 如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。 * * 【难度】 * 中等 * * 【解答】 * 遍历整棵树当然可以求出节点数，但这肯定不是最优解法，本文不再详述。 * * 如果完全二叉树的层数为h，本文的解法可以做到时间复杂度为O(h^2)，具体过程如下： * １、如果head==null，说明是空树，直接返回０。 * ２、如果不是空树，就求树的高度，求法是找到树的最左节点看能到哪一层，层数记为h。 * ３、这一步是求解的主要逻辑，也是一个递归过程记为bs(node,l,h)，node表示当前节点，l表示node所在的层数，h表示整棵树的 * 层数是始终不变的。bs(node,l,h)的返回值表示以node为头的完全二叉树的节点数是多少。初始时node为头节点head，l为１，因 * 为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 */
