关于 222 题求二叉树节点的题目想请教老师

来源：7-2 一个简单的二叉树问题引发的血案 Invert Binary Tree

Osuribaba

2020-10-22

请问老师，关于第 222 号求满二叉树节点的这题，我只想到了递归以及遍历一遍两种方法，但是这两种方法都没有利用到满二叉树这个性质，实在想不到该如何利用满二叉树这个条件来更好的解题了，所以请教老师一下。谢谢

写回答

1回答

liuyubobobo

2020-10-23

已采纳

首先，你的描述有误。222 题的二叉树是一棵完全二叉树，不是满二叉树。一般定义满二叉树最后一层的节点是满的；完全二叉树最后一层的节点可以不满，但一定都靠左。对于一个有 d 层的满二叉树，节点总数直接可以用 2^d - 1 计算出来。

我的做法：

从根节点出发，一直向左走，计算树的高度，再一直向右走，计算树的高度。

如果两个高度一致，说明这是一棵满二叉树，直接用公式求解。否则，这是一棵完全二叉树，但不满。根据完全二叉树的定义，这个根节点的左右子树肯定也是完全二叉树。可以递归地对左右子树继续这个过程求解。

继续加油！：）

Osuribaba

非常感谢！

2020-10-25

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 2

回答 2

回答 1

回答 1

回答 1