二叉（搜索）树转换/完全二叉树验证解析
1.二叉树完全性检验（958-中）
题目描述：给定一个二叉树，确定它是否是一个完全二叉树。百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
示例：
输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
思路：题目转换一下，关键是：层序遍历过程中，遇到第一个空节点之后不应该再出现非空节点，即到达最后一层。具体实现是：定义一个boolean型变量，记录是否到达最后一行（当node == null，按照最后一行进行验证），当到达最后一行并出现非空节点，则不满足。
注意：当node == null，终止下一层的节点加入（cotinue），依次弹出队列元素判断。
代码实现：
public boolean isCompleteTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean isEnd = false;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (isEnd && node != null ) {
return false;
}
if (node == null) {
isEnd = true;
continue;
}
queue.add(node.left);
queue.add(node.right);
}
return true;
}
2.完全二叉树的节点个数（222-中）
题目描述：给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例：
输入：root = [1,2,3,4,5,6]
输出：6
思路：如果没有约束，求二叉树的节点个数，直接递归即可，很简单。显然对于完全二叉树，我们知道满二叉树的节点数为2^h - 1，那么我们可以对root的左右子树的高度进行统计，（子树是满二叉树加上root节点，刚好2^h个），迭代递归实现：
- 如果两者高度相同，左子树为满二叉树，递归右子树
- 否则（左子树高度大于右子树高度），右子树为满二叉树；继续递归左子树
迭代注意更新，左子树的高度，--left。
代码实现：
// 递归
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int left = countLevel(root.left);
int right = countLevel(root.right);
if (left == right) {
return countNodes(root.right) + (1 << left);
} else {
return countNodes(root.left) +(1 << right);
}
}
private int countLevel(TreeNode root) {
if (root == null) {
return 0;
}
return countLevel(root.left) + 1;
}
// 迭代
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int count = 0;
int left = countLevel(root.left);
while (root != null) {
int right = countLevel(root.right);
if (left == right) {
count += (1 << left);
root = root.right;
} else {
count += (1 << right);
root = root.left;
}
--left;
}
return count;
}
private int countLevel(TreeNode root) {
if (root == null) {
return 0;
}
int level = 0;
while (root != null) {
root = root.left;
++level;
}
return level;
}
拓展（T662）：给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
思路分析：修改二叉树的值，根据宽度定义，我们直接利用编号进行求解。
题目中定义的宽度，刚好对应完全二叉树的特性，每一层的层宽，等于完全二叉树中对应节点的编号差，以题目中的 case 作为示例
1
/ \
3 2
/ \ \
5 3 9
节点在满二叉树中的编号值
0
/ \
1 2
/ \ \
3 4 6
很明显 层宽 = 每一层的最右侧编号 - 最左侧编号 + 1
代码实现：
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
Deque<TreeNode> queue = new LinkedList<>();
root.val = 0;
queue.add(root);
int size;
int ans = 0;
while (!queue.isEmpty()) {
size = queue.size();
ans = Math.max(ans, queue.peekLast().val - queue.peekFirst().val + 1);
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
node.left.val = node.val * 2 + 1;
}
if (node.right != null) {
queue.add(node.right);
node.right.val = node.val * 2 + 2;
}
}
}
return ans;
}
3.有序数组转二叉搜索树（108-易）
题目描述：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
思路：题目要求高度平衡，使用分治的思想，找到中间节点。
代码实现：
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(nums, 0, nums.length - 1);
}
private TreeNode toBST(int[] nums, int sIdx, int eIdx){
if (sIdx > eIdx) {
return null;
}
int mIdx = sIdx + (eIdx - sIdx) / 2;
TreeNode root = new TreeNode(nums[mIdx]);
root.left = toBST(nums, sIdx, mIdx - 1);
root.right = toBST(nums, mIdx + 1, eIdx);
return root;
}
拓展：有序链表转二叉搜索树（109-中）
思路：思路同上，技巧：使用快慢指针找链表中间节点的前驱节点！注意：递归之前不要忘记断开链表。
代码实现：
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
ListNode preMid = preMid(head);
ListNode mid = preMid.next;
preMid.next = null;
TreeNode root = new TreeNode(mid.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
public ListNode preMid(ListNode head) {
ListNode slow = head, fast = head;
ListNode preMid = null;
while (fast != null && fast.next != null) {
preMid = slow;
slow = slow.next;
fast = fast.next.next;
}
return preMid;
}
注意：上边在找链表中间节点时，需要遍历链表的一半，时间复杂度O(n)，这里可以利用中序遍历进行优化！设置一个全局的变量遍历链表，在遍历的过程中构建二叉搜索树。
ps：构建树时，注意两个边界不能越界（保证l < r）
private ListNode globalNode;
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
globalNode = head;
int length = getLength(head);
return buildTree(head, 0, length - 1);
}
private TreeNode buildTree(ListNode head, int l, int r) {
if (l > r) {
return null;
}
int mid = l + (r - l) / 2;
// 先建一个节点，等遍历到该位置赋值
TreeNode root = new TreeNode();
root.left = buildTree(head, l, mid - 1);
root.val = globalNode.val;
globalNode = globalNode.next;
root.right = buildTree(head, mid + 1, r);
return root;
}
private int getLength(ListNode head) {
int ans = 0;
while (head != null) {
++ans;
head = head.next;
}
return ans;
}
4.二叉树展开为链表（114-中）
题目描述：给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
进阶：原地算法展开，O(1)空间复杂度。
示例：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
思路：本题如果直接使用额外空间（便于记录树的结构），比较简单。这里补一个非递归的先序遍历复习（模拟递归栈，注：栈的底层是数组，可以存储null值）。最后要将他转化为树。
另解@明知山有虎？：直接递归去求解，递归函数的作用就是讲一个二叉树原地展开为链表，不管内部细节。
-
递归的基本逻辑就是下图连接上的逻辑（丝滑）。
代码实现：
// 迭代
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
continue;
}
list.add(node);
stack.push(node.right);
stack.push(node.left);
}
int size = list.size();
for (int i = 1; i < size; ++i) {
TreeNode pre = list.get(i - 1), cur = list.get(i);
pre.left = null;
pre.right = cur;
}
}
// 递归
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.left);
flatten(root.right);
TreeNode tmp = root.right;
root.right = root.left;
root.left = null;
while (root.right != null) {
root = root.right;
}
root.right = tmp;
}
5.恢复二叉搜索树（99-中）
题目描述：给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
思路：本题的难点，找到那两个点然后把它们交换过来就行了。利用中序升序这一特点。我们只需要找到不满足严格升序的两个节点交换即可。主要还是考察中序遍历。递归和迭代实现，注意两点：
-
定义一个preNode遍历二叉搜索树，用于节点值的比较。注意赋值：第一个是preNode；第二个是cur。
-
找到两个错误点，直接在主函数交换节点值
代码实现：
// 递归
TreeNode firstNode = null;
TreeNode secondNode = null;
TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
inorder(root);
int tmp = firstNode.val;
firstNode.val = secondNode.val;
secondNode.val = tmp;
}
private void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
if (firstNode == null && preNode.val > root.val) {
firstNode = preNode;
}
if (firstNode != null && preNode.val > root.val) {
secondNode = root;
}
preNode = root;
inorder(root.right);
}
// 迭代
TreeNode firstNode = null;
TreeNode secondNode = null;
TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
if (root == null) {
return;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (firstNode == null && preNode.val > cur.val) {
firstNode = preNode;
}
if (firstNode != null && preNode.val > cur.val) {
secondNode = cur;
}
preNode = cur;
cur = cur.right;
}
int tmp = firstNode.val;
firstNode.val = secondNode.val;
secondNode.val = tmp;
}
6.合并二叉树（99-中）
题目描述：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例：
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
合并必须从两个树的根节点开始。
思路：递归实现简单，这里我们以t1作为母树。也可以重新创建一个新二叉树（题目要求）。
迭代：这里以左子树为母树（或者新建节点），当这个节点的左子树为空，那么我们连接另一个树的左子树，反之亦然。当都不为空时，加入队列。
代码实现：
// 递归
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
t1.val += t2.val;
// TreeNode merged = new TreeNode(t1.val + t2.val);
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
// 迭代
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null || t2 == null) {
return t1 == null ? t2 : t1;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.add(t1);
queue.add(t2);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
node1.val += node2.val;
if (node1.left != null && node2.left != null) {
queue.add(node1.left);
queue.add(node2.left);
} else if (node1.left == null) {
node1.left = node2.left;
}
if (node1.right != null && node2.right != null) {
queue.add(node1.right);
queue.add(node2.right);
} else if (node1.right == null) {
node1.right = node2.right;
}
}
return t1;
}
补充.二叉树的（中序遍历）下一个节点（！）
题目描述：给定二叉树其中的一个结点，请找出其中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，而且包含指向父结点的指针。
思路分析：
节点(设为x)中序遍历的下一个节点有以下可能：
（1）若x有右子树。则x的下一个节点为x右子树最左侧节点。如，2的下一个节点为8。
（2）若x没有右子树，又分为2种情况。
- 若x是父节点的左孩子。则x的父节点就是x的下一个节点。如，7的下一个节点是4。
- 若x是父节点的右孩子。则沿着父节点向上，直到找到一个节点的父节点的左孩子是该节点，则该节点的父节点就是x的下一个节点。如，9的下一个节点是1。
注意：关键理解next指针是指向父节点的指针！
代码实现：
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode == null) {
return null;
}
if (pNode.right != null) {
pNode = pNode.right;
while (pNode.left != null) {
pNode = pNode.left;
}
return pNode;
}
while (pNode.next != null) {
if (pNode.next.left == pNode) {
return pNode.next;
}
pNode = pNode.next;
}
return null;
}
}
测试地址：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e
补充：T117， 给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：你只能使用常量级额外空间。使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
思路分析：本题基于二叉树的层次遍历，next节点初始都是指向null的。关键点：定义一个pre指针，进行更新和连接！
代码实现：
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
Deque<Node> queue = new LinkedList<>();
queue.add(root);
int size = 0;
while (!queue.isEmpty()) {
size = queue.size();
Node pre = null;
for (int i = 0; i < size; ++i) {
Node node = queue.poll();
if (pre != null) {
pre.next = node;
}
pre = node;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return root;
}
}
补充：修剪二叉树
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。返回移除了所有不包含 1 的子树的原二叉树。( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
解释：当一个子树中不含1那么删除这个子树，注意子树的定义。
思路：自底向上的递归，当这个节点是叶子节点，并且节点值等于0，直接删除（赋值null）
代码实现：
public TreeNode pruneTree(TreeNode root) {
if (root == null) {
return null;
}
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left == null && root.right == null && root.val == 0) {
return null;
}
return root;
}
