二叉（搜索）树转换/完全二叉树验证解析

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