首页 > 代码库 > 二叉树节点个数，叶子个数，第K层个数，最低公共节点

二叉树节点个数，叶子个数，第K层个数，最低公共节点

2024-09-23 01:19:28   220人阅读

1. 节点个数

function getNodeNum(root){
    if(root == null){
        return 0;
    }
    //+1为root的计数
    return getNodeNum(root.left) + getNodeNum(root.right) + 1;
}

2. 叶子个数

function getLeafNum(root){
    if(root == null){
        return 0;
    }
    if(root.left == null && root.right == null){
        return 1;
    }
    return getLeafNum(root.left) + getLeafNum(root.right);
}

3. 第K层节点个数

//递归方法
function getLevelKNum(root,k){
    if(root == null || k < 1){
        return 0;
    }
    if(k == 1){
        return 1;
    }
    return getLevelKNum(root.left,k-1) + getLevelKNum(root.right,k-1);
}
//非递归方法，使用层次遍历，记录每层的节点个数，到达第K层时，返回节点个数
function getLevelKNum2(root,k){
    if(root == null){
        return;
    }
    var queue = [];
    var level = 1;
    queue.push(root);
    while(queue.length > 0){
        var levelSize = queue.length;
        if(level == k){
            return levelSize;
        }
        while(levelSize > 0){
            var node = queue.shift();
            if(node.left){
                queue.push(node.left)
            }
            if(node.right){
                queue.push(node.right)
            }
            levelSize--;
        }
        level++;    
    }
    return 0;
}

4. 二叉树的最低公共节点，判断节点在左右两侧，则根节点(可能为子树根)为最小公共节点，否则在左子树或右子树中递归查找公共节点

function getLastCommonParent(root,node1,node2){
    if(findNode(root.left,node1)){
        if(findNode(root.right,node2)){
            return root;
        }
        else{
            return getLastCommonParent(root.left,node1,node2);
        }
    }
    else{
        if(findNode(root.left,node2)){
            return root;
        }
        else{
            return getLastCommonParent(root.right,node1,node2);
        }
    }
}   
  
function findNode(root,node){
    if(root == null || node == null){
        return false;
    }
    if(root == node){
        return true;
    }
    return findNode(root.left,node) || findNode(root.right,node);
}

 

二叉树节点个数，叶子个数，第K层个数，最低公共节点


联系
我们