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; }
