已知一棵完全二叉树，求其节点的个数

已知一棵完全二叉树，求其节点的个数 要求：时间复杂度低于O(N)，N为这棵树的节点个数

代码

代码语言：javascript复制

package com.algorithm.practice.tree;

public class CompleteTreeNodeNumber {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    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 level, int h) { //以当前node结点为头的树有多少个结点
        if (level == h) { //node为当前结点,level为该结点在第几层,h为固定值,其实就是整个树的高度
            return 1;
        }
        if (mostLeftLevel(node.right, level   1) == h) {//如果当前右子树的最左结点到了最后一层
            return (1 << (h - level))   bs(node.right, level   1, h);//当前结点左子树结点树 bs右结点
        } else {//如果当前结点右子树最左结点没有达到最后一层,那么右子树是一个满二叉树,且高度比左子树少1
            return (1 << (h - level - 1))   bs(node.left, level   1, h);//当前结点右子树结点树 bs左结点
        }
    }

    public static int mostLeftLevel(Node node, int level) {//返回node的最左结点到了哪一层
        while (node != null) {
            level  ;
            node = node.left;
        }
        return level - 1;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        System.out.println(nodeNum(head));

    }

}

时间复杂度

每次遍历查找一个结点,次数是深度logN 最左结点个数是logN 那么总时间复杂度是O(logN^2)

二叉树 遍历

0 人点赞