自学内容网 自学内容网

力扣 LeetCode 222. 完全二叉树的节点个数(Day7:二叉树)

解题思路:

解法一:普通二叉树解法

使用后序遍历

有一行的精简版代码但不利于理解采用的哪一种遍历方式

解法二:利用上完全二叉树的特点

一个指针left,一个指针right

left一直向左遍历,right一直向右遍历,如果深度相同,那么就是满二叉树,就可以用公式2的n次方-1来计算节点个数

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth)return (2 << leftDepth) - 1;

        int lDepth = countNodes(root.left);
        int rDepth = countNodes(root.right);
        int res = 1 + lDepth + rDepth;
        return res;
    }
}


原文地址:https://blog.csdn.net/qq_61504864/article/details/143885712

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!