深度优先遍历 DFS
解题思路
利用后续遍历的递归来解决节点统计的问题；
这里求和的过程没有简写成一行代码，简写后不容易看出来是后续遍历，不易于理解；
使用层序遍历也可求出，复杂度和此方法相同，就不整理了；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树的节点数； -
空间复杂度：
O(n)，其中 n 是二叉树的节点数；空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数；
代码实现
var countNodes = function (root) {
if (root === null) return 0;
// 后续遍历
let leftNum = countNodes(root.left);
let rightNum = countNodes(root.right);
return leftNum + rightNum + 1;
};
深度优先遍历 DFS（利用完全二叉树特性）
解题思路
递归遍历寻找 满二叉树（完美二叉树） 然后通过
2^树的高度-1求出该树的节点数量；可以通过计算子树的左节点和右节点从长度：
- 如果左右节点的数量相等说明是一棵 满二叉树（完美二叉树）；
- 如果左右节点的数量不相等说明不是一棵 满二叉树（完美二叉树） ，需要继续向下寻找 满二叉树（完美二叉树）；
复杂度
-
时间复杂度：
O(logN*logN)，计算树的高度的时间复杂度为O(logN)，每次递归所花费的时间O(logN) -
空间复杂度：
O(logn)，为递归过程中栈的开销，由于题目给定的数是一棵 完全二叉树 ，所以平均情况下为O(logn)；
代码实现
var countNodes = function (root) {
if (root === null) return 0;
let left = root.left;
let right = root.right;
let leftDepth = 0, rightDepth = 0;
while (left) {
left = left.left;
leftDepth++;
}
while (right) {
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return Math.pow(2, leftDepth + 1) - 1;
}
// 后续遍历
let leftNum = countNodes(root.left);
let rightNum = countNodes(root.right);
return leftNum + rightNum + 1;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 129. 求根节点到叶节点数字之和
上一篇
评论
