数据结构(Java)——Day15(二叉树的OJ题目练习2)-创新互联
1. 思路
成都创新互联公司专注于长子企业网站建设,成都响应式网站建设,商城网站开发。长子网站建设公司,为长子等地区提供建站服务。全流程定制网站开发，专业设计，全程项目跟踪，成都创新互联公司专业和态度为您提供的服务(1)如何判断一棵树是否是完全二叉树：分阶段 + 层序遍历
将一棵完全二叉树看作两个阶段
a. 阶段1：此时的阶段都是度为2的节点，从左到右，从上到下遍历，当碰到第一个只有左子树没有右子树(度为1的节点)或者叶子节点时转换阶段，从该节点之后的节点都应该处在阶段2
b. 阶段2：此时的节点全都是叶子节点，碰到一个反列，直接return false
遍历完整个二叉树，没有返回false，则是一颗完全二叉树
注意：当a.中碰到只有右子树没有左子树的节点直接return false即可
2. 实现代码
(1)思路：深度优先遍历：借助栈这个结构进行遍历。
A. 前序优先遍历的非递归：根左右
a. 首先将根节点压入栈中
b. 当栈不为空的时候进行循环。出栈一个节点，则先将其右节点压栈，再将其左节点压栈，如果没有，则不用压栈
注意：为了保证出栈顺序是根左右的顺序，因此压栈的时候是右节点先压栈，左节点后压栈
B. 注意：一个题外话，树的三种深度优先遍历的递归写法的返回值数组ret应该放在递归函数外
不然每次递归调用都会产生一个新的数组ret，每个ret只能保存当前节点的节点值，最终返回的是最外层的ret，导致结果集出错
C. 注意(重中之重)：在Leetcode和牛客中应当避免使用静态变量和静态方法，尽管语法上可能没有错误
a. 原因：每个用户提交的时候，LeetCode后台会给不同的用户创建该类的对象，使用不同的对象调来调用方法来跑测试用例，如果使用静态变量或方法，就会造成其他用户污染数据，造成自己测试用例报错
例如：
用户1：
Solution144 s1 = new Solution144();
用户2：
Solution144 s2 = new Solution 144();
假设用户2使用静态变量来保存最终的结果集，则这个结果集其他用户能够修改，可能将其他用户的结果值错误的拿过来导致报错
b. 示例：
(2)代码实现
(1)思路：
(2)代码实现：
(1)思路：
A. 如何确定一个节点的右子树不为空的时候是否是遍历完毕
B. 循环过程思路：
a. 首先向左下走到底
b. 然后cur = stack.pop();
<1>判断cur的右子树是否处理过了：cur.right == null || cur.right = prev.
处理过，则说明cur可以出栈了，出栈后添加到结果集中
ret.add(cur.val);
//更新指针
prev = cur;
//注意：要将cur置为null，保证下一次循环cur指向新的栈顶，而不是死循环的压栈出栈
cur = null;
<2>若不满足，则说明cur.right != null && cur.right != prev(表示右子树不为空且右子树未被处理过)
因此将cur重新压入栈中，stack.push(cur);
然后让cur = cur.right，先处理右子树
(2)代码实现
(1)思路：递归 + 前序遍历
注意：明确什么时候打印空扩号：当左子树为空，右子树不为空的时候需要打印空扩号，其他情况无需打印空扩号
A. 函数语义：给定一个二叉树的根节点，就能采用前序遍历，将树的所有节点转换为规定的字符串并添加到结果集ret中
B. 终止条件：当待处理的节点走到null的时候返回空字符串
C. 递归过程：
a. 处理根：ret.append(root)
b. 处理左子树：
<1>当左子树不为空的时候
append("(");
递归调用：将root的左子树的所有节点转换为规定的字符串并添加到结果集中
append(")");
<2>当左子树为空，右子树不为空，则打印一个空扩号
c. 处理右子树：
当右子树不为空：
append("(");
递归调用：将root的右子树的所有节点转换为规定的字符串并添加到结果集中
append(")");
(2)代码实现：
236. 二叉树的最近公共祖先 - 力扣（Leetcode）
(1)思路：递归
A. 最近公共祖先：根据题目分析可知，某一个节点x，左子树，右子树三个位置上有两个位置存在p和q，则x是p和q的最近公共祖先。即为下面的描述
B. 一个隐含的点：p和q的位置是固定的，因此不存在p同时出现在两个位置甚至是三个位置，q也是同理。因此实际上这个left + right + mid的值不可能为3，因为p和q这两个节点最多只能占据两个位置
C. left + right + mid的情况：下列 等于1的情况应该是有且只找到一个节点的情况
(2)代码实现
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章题目：数据结构(Java)——Day15(二叉树的OJ题目练习2)-创新互联
文章出自：http://cdiso.cn/article/dhichg.html
