【Data structure & Algorithm】做题笔记-二叉树
二叉树
-
方法论
-
[226] 反转二叉树结构
-
[116] 设置每个节点的右指针指向其相邻右侧节点
-
[114] 将二叉树转换为单链表形式
-
[654] 构建最大优先级的二叉树模型
-
[105] 利用前序或中序遍历结果进行重构操作
-
[106] 综合运用后序遍历与中序遍历数据进行重构操作[方法]
- 方法一：采用前根次序遍历策略实现重构操作[方法]
- 方法二：采用后根次序遍历策略实现重构操作[方法]
- 方法三：基于中根次序策略实施重构操作（不可行方案）
- 方法四：通过层次遍历策略完成重构过程[方法]
-
222-完全二叉树（complete binary tree）的节点个数
-
- 常规解法
- 最优解
-
-
总结：
-
基于遍历序列恢复二叉树的前提
-
若干典型方法
-
二叉树遍历的具体代码架构及其序列特征
方法论
二叉树采用的是基于递归的方法实现遍历操作。编写递归函数的核心在于准确理解其功能与作用，并以此为基础进行逻辑推导；在此过程中应当避免过于深入处理那些复杂而细节繁多的部分。换一种表述方式即为：首先要明确当前 root 结点应有的职责是什么；按照这一核心概念依次处理其子节点；通过这种层级式的操作能够确保最终结果的一致性与正确性。为了实现目标需要将题目需求分解到各个结点（或若干个结点）的具体任务上。
如，计算一棵二叉树共有几个节点：
// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
// base case
if (root == null) return 0;
// 自己加上子树的节点数就是整棵树的节点数
return 1 + count(root.left) + count(root.right);
}在本问题中，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，在本问题中，默认情况下
框架：
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历位置，在此处访问root.val
traverse(root.left)
// 中序遍历位置，在此处访问root.val
traverse(root.right)
// 后序遍历位置，在此处访问root.val
}226-翻转二叉树
Given a root node of a binary tree, perform a mirror-flip on the entire tree.
通过将二叉树中的每个节点的左右子节点调换位置的操作后得到的结果就是完全翻转后的二叉树结构，请参考图示
// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
// 结束递归的条件
if (root == null) {
return null;
}
/**** 前序遍历位置 ****/
// root 节点需要交换它的左右子节点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 让左右子节点继续翻转它们的子节点
invertTree(root.left);
invertTree(root.right);
return root;//注意return的是根节点
}116-填充每个节点的下一个右侧节点指针
主要问题在于如何实现不同子树间节点间的连接操作，默认情况下仅允许单个输入参数的操作体难以满足需求
将递归函数的参数数量设定为两个（输入两个节点），每一次递归调用时，该函数的作用域会形成一个梯形结构，并包含总共六个具体的节点：包括原始输入的两个父节点以及每个父节点对应的左右子节点（即目标5和目标6）。通过这种方式就能使得这两个目标能够被同时访问并处理。
代码如下，示意图如下。
//错误代码，递归函数的参数只有1个
Node connect(Node root) {
if (root == null || root.left == null) {
return root;
}
root.left.next = root.right;
connect(root.left);
connect(root.right);
return root;
} //正确代码，递归函数的参数有2个
//主函数
public Node connect(Node root) {
if(root == null){
return null;
}
connect2Nodes(root.left,root.right);
return root;
}
//辅助函数
public void connect2Nodes(Node n1,Node n2){
//n1在左,n2在右（不要反了）
//结束递归的条件，注意：这是一棵完美二叉树
if(n1 == null || n2 == null){//由于是完美二叉树，n1、n2实际上会同时为null，或同时不为null
return;
}
/**** 前序遍历位置 ****/
// 将传入的两个节点连接
n1.next = n2;
// 连接相同父节点的两个子节点
connect2Nodes(n1.left,n1.right);
connect2Nodes(n2.left,n2.right);
// 连接跨越父节点的两个子节点
connect2Nodes(n1.right,n2.left);
}
114-将二叉树展开为链表
题目
关键点在于想象整个二叉树被展平（Flatten）的过程。通过下图所示的过程详细说明了该过程：其中蓝色方框标识当前关注的二叉树部分，在递归操作中依次处理根节点的左子树、右子树以及整体结构。“展平”具体操作如下：对于根节点而言，在其左子树已经被展平时将其插入到根节点与右子树之间；而对于整体而言，则将已展平后的根节点左子树插入到根节点与其右子树之间。“展平”的核心就是递归处理每个节点及其子树。
public void flatten(TreeNode root) {
if(root == null){
return;
}
//先拉平左子树
flatten(root.left);
//再拉平右子树
flatten(root.right);
/**** 后序遍历位置 ****/
//将拉平后的左子树插入到根节点与右子树之间
TreeNode rootLeft = root.left;
TreeNode rootRight = root.right;
if(rootLeft != null){
root.left = null;
root.right = rootLeft;
//将右子树拼接到原左子树的最右下末端（原左子树已经被flatten过了，一定是\形状）
TreeNode connectNode = rootLeft;
while(connectNode.right != null){
connectNode = connectNode.right;
}
//connectNode为原左子树的最右下末端节点
connectNode.right = rootRight;
}
}654-构造最大二叉树
该问题的目标是构建一棵满足特定条件的最大二叉树。具体来说：
首先确定根节点root即数组中的最大元素；
然后将数组中位于该最大元素左侧的部分构建成一棵最大二叉树，并将其作为当前根节点的左子树；
接着将右侧部分同样构建为另一棵最大二叉树，并将其作为当前根节点的右子树。
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums,0,nums.length-1);
}
public TreeNode build(int[] nums,int start,int end){//start，end表明使用数组哪一步分
if(end < start){
return null;
}
//找数组中的最大值及其索引，作为根节点
int max = nums[start];
int index = start;
for(int i=start+1;i<=end;i++){
if(nums[i] > max){
max = nums[i];
index = i;
}
}
TreeNode root = new TreeNode(max);
//将最大值左边部分构建成最大二叉树,作为根节点的左子树
root.left = build(nums,start,index-1);
//将最大值右边部分构建成最大二叉树，作为根节点的右子树
root.right = build(nums,index+1,end);
return root;
}105-用前序/中序遍历结果还原二叉树
题目
首先看前序遍历和后序遍历的递归代码，代码的结构，决定了遍历结果（数组）的特点。
void traverse(TreeNode root) {
// 前序遍历位置，在此处访问root.val
traverse(root.left);
traverse(root.right);
}
void traverse(TreeNode root) {
traverse(root.left);
// 中序遍历位置，在此处访问root.val
traverse(root.right);
}通过分析代码结构可以看出：前序遍历生成的结果是一个数组，在该数组中根节点位于第一个元素位置之后依次排列着左子树的所有节点接着依次排列着右子树的所有节点；而中序遍历生成的结果也是一个数组，在这个过程中首先是左子树的所有节点随后放置根节点最后依次排列着右子树的所有节点。事实确实如此
了解了前缀序列和中间序列各自的特性后,如何建立一棵二叉树呢？基于前缀序列和中间序列,构建二叉树的过程大致可分为以下几个步骤:首先确定根节点值,并创建初始节点;接着通过分析左半部分中间序列确定左子树结构;同样地,在右半部分中间序列基础上建立右子树。正是我们设计递归算法的核心任务。
请注意：当递归函数接收一个数组作为参数时，可以同时指定该数组的起始索引（start index）和结束索引（end index）。这种做法有助于避免复制现有数组并减少计算开销。
在步骤二至步骤三中进行处理时，请确定每个子树对应的先根序列列表及其中间序列列表。
为了更好地理解这些结构之间的关系。
我们需要明确左子树所占的位置范围（即左子树节点的数量），以便准确计算先根序列列表中左子树占据的位置。
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode build(int[] preorder,int pStart,int pEnd, int[] inorder,int iStart,int iEnd){
if(pStart > pEnd || iStart > iEnd){
return null;
}
//1.先从数组中找出根节点的值，创建根节点
//前序遍历数组的第一个值就是根节点的值
int rootVal = preorder[pStart];
TreeNode root = new TreeNode(rootVal);
//获得根节点在中序遍历数组中的位置
int rootIndex4Inorder = 0;
for(int i=iStart;i<=iEnd;i++){
if(inorder[i] == rootVal){
rootIndex4Inorder = i;
break;
}
}
//得到左子树的长度
int leftTreeSize = rootIndex4Inorder - iStart;
//2.获得左子树的中序遍历数组、前序遍历数组，根据这两个数组构建二叉树作为根节点的左子树
root.left = build(preorder,pStart+1,pStart+leftTreeSize,inorder,iStart,rootIndex4Inorder-1);
//3.获得右子树的中序遍历数组、前序遍历数组，根据这两个数组构建二叉树作为根节点的右子树
root.right = build(preorder,pStart+leftTreeSize+1,pEnd,inorder,rootIndex4Inorder+1,iEnd);
return root;
}106-通过后序和中序遍历结果构造二叉树
此题与上一题具有相似性。首先分析中序遍历过程与后序遍历过程的代码框架：
此题与上一题具有相似性。具体实现时可参考以下中序遍历与后序遍历结合的代码框架：
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
// 后序遍历位置，在此处访问root.val
}
void traverse(TreeNode root) {
traverse(root.left);
// 中序遍历位置，在此处访问root.val
inorder.add(root.val);
traverse(root.right);
}由于这样的代码结构，导致了遍历结果的特点：
- 中序遍历数组：左子树-根节点-右子树
- 后序遍历数组：左子树-右子树-根节点
了解了两种不同遍历方式在数组中的特征后，在深入理解这些特点的基础上去探索如何将这些知识应用到实际问题解决当中。具体来说就是要掌握如何利用前向序列与逆向序列来构造相应的二叉树结构。“基于前向序列与逆向序列构造一棵完整的二叉搜索结构”就是我们递归算法实现的核心逻辑任务
在第2步和第3步的过程中，请您先获取该二叉树的后序序列以及相应的中序序列，并建议绘制一张图以便于理解： 我们需要知道左子树在该序列中的具体长度（即左子树节点的数量），这样才能确定后序序列中左子树所在的结束位置。
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode build(int[] inorder,int inStart,int inEnd,int[] postorder,int poStart,int poEnd){
if(inStart > inEnd || poStart > poEnd){
return null;
}
//1.先从数组中找出根节点的值，创建根节点
//后序遍历数组的最后一个值是根节点值
int rootVal = postorder[poEnd];
TreeNode root = new TreeNode(rootVal);
//获得根节点在中序遍历数组中的位置
int rootIndex4Inorder = 0;
for(int i=inStart;i<=inEnd;i++){
if(inorder[i] == rootVal){
rootIndex4Inorder = i;
break;
}
}
//得到左子树的长度
int leftTreeSize = rootIndex4Inorder - inStart;
//2.获得左子树的中序遍历数组、后序遍历数组，根据这两个数组构建二叉树作为根节点的左子树
root.left = build(inorder,inStart,rootIndex4Inorder-1,postorder,poStart,poStart+leftTreeSize-1);
//3.获得右子树的中序遍历数组、后序遍历数组，根据这两个数组构建二叉树作为根节点的右子树
root.right = build(inorder,rootIndex4Inorder+1,inEnd,postorder,poStart+leftTreeSize,poEnd-1);
return root;
}652-寻找重复的子树
题目
思考以下问题：
1.如何描述一棵二叉树的样子？
如果两棵二叉树的先序、中序或后续遍历结果完全一致，则这两棵二叉树完全相同。我们可以通过将二叉树节点按特定顺序排列生成唯一的序列化表示（ serialization ），其中非数字的特殊符号 # 表示空指针节点，并以逗号分隔各个节点值——这种方法在序列化数据时经常使用。
2.如何确定一棵二叉树的样子？
确定了根节点及其左右子树的样式之后，则整个根节点的样式也随之确定了——换言之，在已知根节点值的前提下，在左子树样式的基础上附加右子树样式即可得到该根节点对应的整个根节点样式。（对应于后续遍历框架）
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
/* 判断以root为根节点的二叉树，是否和其他二叉树一样 */
}如何了解其他二叉树的样子？
Map trees = new HashMap<String,Integer>();
List roots = new LinkedList<TreeNode>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
describe(root);
return roots;
}
public String describe(TreeNode root){
if(root == null){
return "#";
}
//得到root的左子树的遍历序列
String leftTree = describe(root.left);
//得到root的右子树的遍历序列
String rightTree = describe(root.right);
/**后序遍历位置：得到以root为根节点的二叉树的后序遍历序列（描述该二叉树的模样）**/
String description = leftTree + "," + rightTree + "," + root.val;
/**后序遍历位置：判断以root为根节点的二叉树，是否和其他二叉树一样**/
//将该序列存储到Map中
Object freq = trees.get(description);
if(freq == null){//Map中还没有该序列
trees.put(description,1);
}else{//Map中已经存在该序列了
Integer freq_ = (Integer)freq;
trees.put(description,freq_+1);
if(freq_ == 1){//第一次出现重复的时候，将根节点放入List
roots.add(root);
}
}
return description;
}297-二叉树的序列化与反序列化
问题（题目标签）：请完成二叉树的序列化与反序列化
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
}
}在本题中, 我们自行决定序列化流程, 即为二叉树的遍历方式. 即为二叉树的前序遍历方法. 也有中序遍历. 后续还有后续遍历以及层次遍历等多种方法. 那么字符串拼接在时间和空间资源上都有较高的消耗. 因此建议采用StringBuilder类.
方法1：前序遍历
反序列化的时候会利用前序遍历序列的特点：根-左子树-右子树
public class Codec {
//分隔符
String SEP = ",";
//空节点
String NULL = "#";
/* 主函数，将二叉树序列化为字符串 */
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root,sb);
return sb.toString();
}
/* 辅助函数，将二叉树存入 StringBuilder */
public void serialize(TreeNode root,StringBuilder sb){
if(root == null){
sb.append(NULL).append(SEP);//在序列中加入#以表示为空节点
return;
}
/**前序遍历位置**/
sb.append(root.val).append(SEP);//在序列中加入本节点的值
serialize(root.left,sb);
serialize(root.right,sb);
}
/* 主函数，将字符串反序列化为二叉树结构 */
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
//将String转化为List，方便遍历各个值
LinkedList<String> vals = new LinkedList<>();
String[] strArray = data.split(SEP);//以SEP分隔符，获得String数组
for(String val:strArray){
vals.add(val);
}
return deserialize(vals);
}
/* 辅助函数，通过序列构造二叉树 */
public TreeNode deserialize(LinkedList<String> vals){//从前往后在list中取元素
if(vals.isEmpty()){
return null;
}
//任务：构造根节点，构造其左右子树并与根节点相连接
//前序遍历序列的第一个值是根节点
String first = vals.removeFirst();//removeFirst()是LinkedList的方法，移除并返回此列表的第一个元素
if(first.equals(NULL)){//如果是#
return null;
}
//生成根节点
TreeNode root = new TreeNode(Integer.parseInt(first));//String转Integer
//构建左子树二叉树，连接到root
root.left = deserialize(vals);
//构建右子树二叉树，连接到root
root.right = deserialize(vals);
return root;
}
}方法2：后序遍历
反序列化的时候会利用后序遍历序列的特点：左子树-右子树-根
public class Codec {
//分隔符
String SEP = ",";
//空节点
String NULL = "#";
/* 主函数，将二叉树序列化为字符串 */
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root,sb);
return sb.toString();
}
/* 辅助函数，将二叉树存入 StringBuilder */
public void serialize(TreeNode root,StringBuilder sb){
if(root == null){
sb.append(NULL).append(SEP);//在序列中加入#以表示为空节点
return;
}
serialize(root.left,sb);
serialize(root.right,sb);
/**后序遍历位置**/
sb.append(root.val).append(SEP);//在序列中加入本节点的值
}
/* 主函数，将字符串反序列化为二叉树结构 */
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
//将String转化为List，方便遍历各个值
LinkedList<String> vals = new LinkedList<>();
String[] strArray = data.split(SEP);//以SEP分隔符，获得String数组
for(String val:strArray){
vals.add(val);
}
return deserialize(vals);
}
/* 辅助函数，通过序列构造二叉树 */
public TreeNode deserialize(LinkedList<String> vals){//从后往前在list中取元素
if(vals.isEmpty()){
return null;
}
//任务：构造根节点，构造其左右子树并与根节点相连接
//后序遍历序列的最后一个值是根节点
String first = vals.removeLast();//removeLast()是LinkedList的方法，移除并返回此列表的最后一个元素
if(first.equals(NULL)){//如果是#
return null;
}
//生成根节点
TreeNode root = new TreeNode(Integer.parseInt(first));//String转Integer
//注意：后序遍历序列特点为左子树-右子树-根，我们从后往前取元素，所以要先构建右子树
//先构建右子树二叉树，连接到root
root.right = deserialize(vals);
//再构建左子树二叉树，连接到root
root.left = deserialize(vals);
return root;
}
}方法3：中序遍历（行不通）
采用中序遍历方法可以实现数据的编码。然而，在反序列化过程中则面临挑战：由于缺乏初始数据结构中的根节点信息，在缺少该关键数据的情况下难以直接恢复原始结构。完成解码所需的步骤首先是确定并建立一个空的树结构，并通过后续操作逐步填充其各个分支。随后的工作便是逐步构建左子树和右子树。其中，在前缀编码（pre-order）过程中首字母通常位于左端位置；而在后缀编码（post-order）策略下，则需关注编码末尾的部分；而对于中缀方式（in-order）所生成的数据流，则需特别留意中间部分的位置特征才能正确恢复原生结构的信息完整性。
方法4：层级遍历
特殊的数据结构Queue是一种特殊的容器，在其头部被限制仅能在容器头部执行删除操作，在尾部执行插入操作。而LinkedList类作为一个实现了接口的数据结构，则被当作一种实现Queue的方式使用。该接口定义了两个基本方法：提供一个后端插入的操作，并执行前端取出的操作。
经典的二叉树层次遍历结构，在打印每一层节点值时总是按照自上而下的顺序进行，并且观察发现队列 q 中不会出现空指针。
void traverse(TreeNode root) {
if (root == null) return;
// 初始化队列，将 root 加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
/* 层级遍历代码位置 */
System.out.println(root.val);
/*****************/
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}结合自己的需求，把上边框架改一下，就能实现序列化。
解码过程需要分析遍历序列的特征（如图1所示），并据此设计构建二叉树的过程。所谓构建的过程就是：首先确定根节点；接着找出根节点的左子节点，并将其与其连接；同样的方法用于右子节点；依次类推...完成整个二叉树的重建。
初始化一个指针变量用于从左到右遍历数组，并需引入一个队列数据结构来存储尚未有子节点的根节点。为什么需要这个队列？因为当指针移动至第一个#标记时，系统无法立即识别其对应的根节点信息，因此必须借助辅助数据结构来进行追踪。具体来说，在某个节点作为子节点时（即该节点具有子树结构），该父节点会被提前加入到队列中；而在该父节点自身成为根节点的情况下，则会按照先进先出的原则依次移除并处理各子树信息。
public class Codec {
//分隔符
String SEP = ",";
//空节点
String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null){
return "";
}
//创建队列，存放层级遍历顺序的节点
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()){//当队列中存在节点时
//从队列中取节点
TreeNode cur = queue.poll();
/* 层级遍历代码位置 */
if(cur == null){
sb.append(NULL).append(SEP);
continue;//跳到下一次循环
}
sb.append(cur.val).append(SEP);
//往队列里存节点
queue.offer(cur.left);
queue.offer(cur.right);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.isEmpty()){
return null;
}
String[] array = data.split(SEP);
//创建根节点（层序遍历序列的第一个值是根节点值）
TreeNode root = new TreeNode(Integer.parseInt(array[0]));
//该队列用来存放尚未连接子节点的根节点
Queue<TreeNode> rootQ = new LinkedList<>();
rootQ.offer(root);
int index = 0;//指示进行到数组中哪个位置
while(index < array.length-1){//每次循环处理一对左右节点（2个节点），所以要-1
//队列中取出根节点
TreeNode parent = rootQ.poll();
//获取左节点的值
String leftNode = array[++index];
if(!leftNode.equals(NULL)){
//创建左节点，并连接到根节点
parent.left = new TreeNode(Integer.parseInt(leftNode));
//将该节点放进队列
rootQ.offer(parent.left);
}else{
parent.left = null;
}
//获取右节点的值
String rightNode = array[++index];
if(!rightNode.equals(NULL)){
//创建右节点，并连接到根节点
parent.right = new TreeNode(Integer.parseInt(rightNode));
//将该节点放进队列
rootQ.offer(parent.right);
}else{
parent.right = null;
}
}
return root;
}
}222-完全二叉树（complete binary tree）的节点个数
常规解法
计算一棵二叉树的节点，这很简单，递归就行：
// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
// base case
if (root == null) return 0;
// 自己加上子树的节点数就是整棵树的节点数
return 1 + count(root.left) + count(root.right);
}节点数量为N，则该算法的时间复杂度为O(N)。那么计算过程是怎样的呢？递归深度（亦称次数）乘以每轮的计算量等于N乘以1等于N。
最优解
然而题目指出该数据结构为完全二叉树，并且若充分运用其属性，则可能具备效率更高的解决方案
这个题目有如下关键点：
-
- 掌握完全二叉树的概念及其内涵
-
- 熟悉满二叉树节点结构特点，并可利用预设模式进行计算
英文：
完全二叉树-complete binary tree
满二叉树-perfect binary tree
完全二叉树的定义
题目所述：完全二叉树是指除了某一层最后一个节点为空外的所有其他层均已填满最大数量的节点，并且最后一层的所有节点都集中于该层最左侧的位置。若某一层为第 h 层，则该层最多可容纳从1到2^h个节点。
满二叉树的定义
每层都充满节点是很容易理解的。
一个深度为h的满二叉树共有：
1 + 2 + 2² + … + 2^h个节点
这是一个等比数列求和的问题，请使用等比数列求和公式计算总数
可得节点数N=2^h-1
注意：高度被定义为边的数量而非节点的数量，在图中所示的满二叉树中其高度是2而非3
因此我们掌握了普通二叉_tree节点数量通过递归来计算的方法_其时间复杂度为O(N)而完整双子树叶的数量则可通过直接套用公式得出_显而易见的是_完整双子_tree的计算过程远比其他类型简单得多_于是我们将二者结合起来_在递归的过程中_如果当前轮次处理的是一个完整的（即完全或完美）的过程_就可以直接套用公式完成计算_如何确定一棵完整的或者说是完美的（Perfect Binary Tree）结构呢？如上图所示_其左分支和右分支的高度相等则判定该棵树属于完美型结构
public int countNodes(TreeNode root) {
TreeNode leftTreeRoot = root;
TreeNode rightTreeRoot = root;
//得到左边线的长度（注意：高度是边的个数，不是节点个数）
int leftTreeHeight = 0;
while(leftTreeRoot != null){
leftTreeHeight++;
leftTreeRoot = leftTreeRoot.left;
}
//得到右边线的长度
int rightTreeHeight = 0;
while(rightTreeRoot != null){
rightTreeHeight++;
rightTreeRoot = rightTreeRoot.right;
}
if(leftTreeHeight == rightTreeHeight){//如果两边线的长度相同，说明是一棵满二叉树，可以直接使用公式
return (int)Math.pow(2,leftTreeHeight)-1;
}
//以当前root为根节点的树不是满二叉树时，继续递归
return 1+countNodes(root.left)+countNodes(root.right);
}时间复杂度分析：
一棵完全二叉树的左右子树中必有一个子树为满二叉树，在该子树上可以直接应用公式计算返回值，在另一棵子树上则需采用递归方法进行处理。每层递归时，循环的次数等于该层节点的数量。计算如下：节点数N满足关系式 N=2^h -1，则该层的高度 h=log(N+1)；因此，在该层递归中所消耗的时间复杂度为O(logN)
该算法的递归深度相当于树的高度为 O(\log N)；每次递归所需时间相当于 while 循环所需时间 O(\log N)；因此整体时间复杂度达到 O(\log^2 N)
这里理解的不是很透彻…
总结
规划好这个递归函数的任务及其输入变量后，请明确该函数的作用即为：基于特定的输入变量来执行特定的操作。切勿深入细节
根据遍历序列还原二叉树的条件
若序列中无空节点的数据（例如：1 2 4 3 等），则需具备前序和中序或前序和后序两种遍历序列才能恢复二叉树结构；
反之若序列中含有空节点的数据（例如：1 2 # 4 # # 3 # # 等），则仅需采用一种特定的遍历顺序便能恢复二叉树结构。
一些常用方法
队列（Queue）定义如下：
提供一个向尾部添加元素的操作。
获取或移除从头部取出元素的操作。
创建：
Queue
StringBuilder：
append-追加
LinkedList：
移除第一个元素并返回其值
移除最后一个元素并返回其值
Math.pow(底数,幂) :求几次方
二叉树遍历的代码框架、序列特点
前序、中序、后序：
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历位置，在此处访问root.val
traverse(root.left)
// 中序遍历位置，在此处访问root.val
traverse(root.right)
// 后序遍历位置，在此处访问root.val
}层级：
void traverse(TreeNode root) {
if (root == null) return;
// 初始化队列，将 root 加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
/* 层级遍历代码位置 */
System.out.println(root.val);
/*****************/
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}前根：首先处理主节点（根），接着依次处理左子树和右子树；中根：中间处理主节点（根）；后根：最后处理主节点（根）；层进：层次递进地组织信息