数据结构(Java)——Day15(二叉树的OJ题目练习2)-创新互联

1. 二叉树的完全性校验：958. 二叉树的完全性检验 - 力扣（Leetcode）

1. 思路

成都创新互联公司专注于长子企业网站建设,成都响应式网站建设,商城网站开发。长子网站建设公司,为长子等地区提供建站服务。全流程定制网站开发，专业设计，全程项目跟踪，成都创新互联公司专业和态度为您提供的服务

(1)如何判断一棵树是否是完全二叉树：分阶段 + 层序遍历

将一棵完全二叉树看作两个阶段

a. 阶段1：此时的阶段都是度为2的节点，从左到右，从上到下遍历，当碰到第一个只有左子树没有右子树(度为1的节点)或者叶子节点时转换阶段，从该节点之后的节点都应该处在阶段2

b. 阶段2：此时的节点全都是叶子节点，碰到一个反列，直接return false

遍历完整个二叉树，没有返回false，则是一颗完全二叉树

注意：当a.中碰到只有右子树没有左子树的节点直接return false即可

2. 实现代码

2. 前序遍历的非递归写法：144. 二叉树的前序遍历 - 力扣（Leetcode）

(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)代码实现

3. 中序遍历的非递归写法：94. 二叉树的中序遍历 - 力扣（Leetcode）

(1)思路：

(2)代码实现：

4. 后序遍历的非递归写法：145. 二叉树的后序遍历 - 力扣（Leetcode）

(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)代码实现

5. 根据二叉树创建字符串：606. 根据二叉树创建字符串 - 力扣（Leetcode）

(1)思路：递归 + 前序遍历

注意：明确什么时候打印空扩号：当左子树为空，右子树不为空的时候需要打印空扩号，其他情况无需打印空扩号

A. 函数语义：给定一个二叉树的根节点，就能采用前序遍历，将树的所有节点转换为规定的字符串并添加到结果集ret中

B. 终止条件：当待处理的节点走到null的时候返回空字符串

C. 递归过程：

a. 处理根：ret.append(root)

b. 处理左子树：

<1>当左子树不为空的时候

append("(");

递归调用：将root的左子树的所有节点转换为规定的字符串并添加到结果集中

append(")");

<2>当左子树为空，右子树不为空，则打印一个空扩号

c. 处理右子树：

当右子树不为空：

append("(");

递归调用：将root的右子树的所有节点转换为规定的字符串并添加到结果集中

append(")");

(2)代码实现：

6. 二叉树的最近公共祖先：

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://dzwzjz.com/article/dhichg.html