考试重点，二叉树

1. 树的基本结构和定义

节点的定义，每个节点有val，和左右孩子:

public static class Node {
    int value;
    Node left;
    Node right;

    public Node(int data){
        this.value = data;
    }
}

1. 满二叉树(full binary tree), 除叶子结点外所有的节点都有两个子结点。
2. 完全二叉树(complete binary tree), 满树或依次正在变成满树。
3. 树的最大深度, 从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

2. 树的广度优先遍历-递归

在递归函数中，树的递归有它的递归序，在递归序列中第几次打印自己就对应着不同的递归顺序。
1.先序遍历
<root> <left> <right>
第一次来到这个节点就打印，说明先遍历了根节点。

// 1. 先序遍历
public static void preOrder(Node head){
    if(head == null){
        return;
    }
    System.out.print(head.value + " ");
    preOrder(head.left);
    preOrder(head.right);
}

2.中序遍历
<left> <root> <right>
第二次来到这个节点就打印，说明我的左子树已经打印完毕了。
特别用法: 中序遍历可以依次顺序的打印出，搜索二叉树上面的数据。

// 2. 中序遍历
public static void inOrder(Node head){
    if(head == null){
        return;
    }
    inOrder(head.left);
    System.out.print(head.value + " ");
    inOrder(head.right);
}

3.后序遍历
<left> <right> <root>
第三次来到这个节点就打印，说明我的左右子树都已经打印完毕了。
特别用法: 后序遍历可以依次删除节点，用在c++中析构整棵树。

// 3. 后序遍历
public static void postOrder(Node head){
    if(head == null){
        return;
    }
    postOrder(head.left);
    postOrder(head.right);
    System.out.print(head.value + " ");
}

3. 树的宽度优先遍历-LevelOrder

树的层次遍历，可以逐层的遍历所有的节点。借助数据结构: 队列的先进先出，先压入头节点，每次弹出队首，再检查弹出节点的左右孩子，如果有则压入，直到队列为空。

public static void levelOrder(Node head) {
    if (head==null) {
        return;
    }
    Queue<Node> queue = new LinkedList<Node>();
        //先压入头节点，初始化
    queue.offer(head);
    while(!queue.isEmpty()){
        //每次弹出一个节点
        head = queue.poll();
        System.out.print(head.value + " ");
        // 再入队它的左右孩子
        if(head.left!=null){
            queue.offer(head.left);
        }
        if(head.right!=null){
            queue.offer(head.right);
        }
    }
    System.out.println();
}

4. 递归模版

总结：
首先是考虑base case，叶子结点的返回情况，也就是当(node==null)时；然后接收左右子树返回的信息，整理出我需要的信息，把这些信息的返回值在左树和右树上求并集，对于所有的递归节点都一视同仁。

4.1 求高度

解法一: 递归方法

二叉树的高度定义为，从根节点到某个叶子节点的最长路径。这个问题可以用递归分解成，从叶子节点起，求每个以它为头节点的树的高度，逐次向上返回，每次判断左右子树的高度，取大值。
这里注意，在base case 时返回的是-1还是0，根据题目要求。
需要返回: 左右子树的高度leftHeight 和 rightHeight
整合信息: max(leftHeight, rightHeight) + 1

/*

@ 题目：求二叉树的高度
@ 解法：采用分治的思想，求左树的高度，再求右树的高度，最后根节点的高度就是
  Max(leftsubtree.height, rightsubtree.height) + 1
@ base case: 当head为空时，就是叶子结点的左右树，此时返回-1，这样叶子结点的高度才是0
*/
public static int treeHeight(Node head){
    if (head == null){
        return -1;
    }
    int leftHeight = treeHeight(head.left);
    int rightHeight = treeHeight(head.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

方法二: 非递归方法，层次遍历求最后一层

层次遍历，返回最后一个节点的level就是树的高度

public int maxDepth(TreeNode root) {
    // 层次遍历
    if(root==null){
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    HashMap<TreeNode, Integer> levelMap = new HashMap<TreeNode, Integer>();
    queue.offer(root);
    levelMap.put(root, 1);
    TreeNode node = root;
    while(!queue.isEmpty()){
        node = queue.poll();
        int curLevel = levelMap.get(node);
        if(node.left!=null){
            queue.offer(node.left);
            levelMap.put(node.left, curLevel+1);
        }
        if(node.right!=null){
            queue.offer(node.right);
            levelMap.put(node.right, curLevel+1);
        }
    }
    return levelMap.get(node);
}

4.2 验证平衡二叉树

定义:
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
解法:
需要的信息:1.左树是平衡的；2.右树是平衡的 3.左右树的高度差不超过一
需要构造一个返回类，里面有 是否平衡 和 树的高度 两个信息
base case: if root==null 则 返回 new ReturnData(true, 0)，表示空节点高度为0，且平衡
合并信息:
isBalanced = leftData.isBalanced && rightData.isBalanced && 高度差小于2
height = max(左高度，右高度) + 1
时间复杂度 O(N)
空间复杂度 O(N)

// 定义递归返回信息类型
public static class ReturnData {
    boolean isBT;
    int height;

    ReturnData(boolean isBT, int height){
        this.isBT = isBT;
        this.height = height;
    }

// 递归本体
public static ReturnData isBalanced_process(Node root) {
    if(root==null){
        return new ReturnData(true, 0);
    }

    // 从左右返回信息
    ReturnData leftData = isBalanced_process(root.left);
    ReturnData rightData = isBalanced_process(root.right);

    // 整合信息:左树平衡，右树平衡，且高度差不超过一
    int height = Math.max(leftData.height, rightData.height) + 1;
    boolean isBT = leftData.isBT && rightData.isBT && (Math.abs(leftData.height - rightData.height)<2);
    return new ReturnData(isBT, height);
}
}

4.3 验证搜索树

二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解法一: 递归
分析可知，需要满足如下条件

1. 左子树整体是 搜索树
2. 右子树整体是 搜索树
3. 左子树的max < x < 右子树的min

返回的信息类需要包含, 左树的max，右树的min，本身的isBST
base case: 如果为空，则返回 null ，在整合信息时处理null的情况
整合信息:
如果左不为空
max = Max(max, leftData.max)
min = Min(min, leftData.min)
如果右不为空
max = Max(max, rightData.max)
min = Min(min, rightData.min)
逻辑整合，要区分非空情况:
为空时，返回true，因为叶子节点的左右空节点不影响逻辑判断
left_isBST = leftData!=null ? (leftData.isBST && leftData.max <= head.value) : true;
right_isBST = rightData!=null ? (rightData.isBST && rightData.min > head.value) : true;
isBST = left_isBST && right_isBST;

时间复杂度 O(N)
空间复杂度 O(N)

// 返回的信息类
ReturnData(boolean is, int min, int max){
    this.isBST = is;
    this.min = min;
    this.max = max;
    }
}

public static ReturnData recursiveProcess(Node head) {
    // base case
    if(head==null){
        return null;
    }
    // 接受左右返回信息
    ReturnData leftData = recursiveProcess(head.left);
    ReturnData rightData = recursiveProcess(head.right);

    // 整合信息: 整合min和max, 若左右子树为空，当前节点的min和max都是node节点自身无需比较
    int min = head.value;
    int max = head.value;
    // 若左右子树不为空，更新
    // 节点的左子树只包含小于当前节点的数。
    // 节点的右子树只包含大于当前节点的数。
    if(leftData!=null){
        max = Math.max(max, leftData.max);
        min = Math.min(min, leftData.min);
    }
    if(rightData!=null){
        max = Math.max(max, rightData.max);
        min = Math.min(min, rightData.min);
    }
    // 整合isBST
    boolean isBST = false;
    // 左树和node达标：左子树整体是BST 且 左树的max小于node
    boolean condition_1 = leftData!=null ? (leftData.isBST && leftData.max <= head.value) : true;
    // 右树和node达标：右子树整体是BST 且 右树的min大于node
    boolean condition_2 = rightData!=null ? (rightData.isBST && rightData.min > head.value) : true;
    if(condition_1 && condition_2){
        isBST = true;
    }
    return new ReturnData(isBST, min, max);
}

解法二: 中序遍历, 验证输出序列是否是升序

// 用非递归的中序遍历整颗树，判断是否是升序
public static boolean isBST_inOrder(Node head) {
    if (head==null){
        return true;
    }
    Stack<Node> stack = new Stack<>();
    Node node = head;
    double pre = Double.MIN_VALUE;
    while(!stack.isEmpty() || node!=null){
        // 左遍历
        if(node!=null){
            stack.push(node);
            node = node.left;
        }
        // 退出左遍历，先弹出一个节点，在对右节点执行左遍历
        else{
            node = stack.pop();
                        // 验证升序，一旦不符合，直接返回结果，比递归版本好
            if(node.value <= pre){
                return false;
            }
            pre = node.value;
            node = node.right;
        }
    }
    return true;
}

4.4 验证满树

如果一棵树是满树，则他的高度是h，节点总计N，则满足N=2ˆh-1
方法一: 递归
需要返回的信息包含: 节点数nodes 和 树的高度 height
base case: ReturnData(0,0)表示空节点，高度为零，节点数也是零
整合信息:
height = max(leftHeight, rightHeight) + 1
nodes = leftNodes + rightNodes + 1

// 定义递归返回信息类型
public static class ReturnData {
    int height;
    int num;

ReturnData(int height, int num){
    this.height = height;
    this.num = num;
}
}

public static ReturnData process (Node root){
    // base case
    if(root==null){
        // 空节点返回(0,0)
        return new ReturnData(0,0);
    }
    // 从左右返回信息
    ReturnData leftData = process(root.left);
    ReturnData rightData = process(root.right);

    // 整合信息
    int height = Math.max(leftData.height, rightData.height) + 1;
    // 节点总数: 左 + 右 + 自己
    int num = leftData.num + rightData.num + 1;
    return new ReturnData(height, num);
}
// 最后检查，是否满足公式
public static boolean isFull (Node root){
    if(root == null){
        return true;
    }
    ReturnData data = process(root);
        // 1 << N 表示 2的N次幂
    boolean res = data.num == (1 << data.height) - 1;
    System.out.println(data.num);
    System.out.println(data.height);
    return res;
}

方法二: 层次遍历，统计高度和总的节点数

// 非递归方法: 层次遍历，用HashMap记录，每个节点的层数，最后一个节点的层数，雨总的节点数对比
public static boolean isFull_LevelOrder(Node root) {
    if(root == null){
        return true;
    }
        // 队列用于层次遍历
    Queue<Node> queue = new LinkedList<Node>();
        // HashMap用于记录层数
    HashMap<Node, Integer> levelMap = new HashMap<>();
    queue.offer(root);
    levelMap.put(root, 1);
    int curLevel = 0;
    Node node = root;
    while(!queue.isEmpty()){
        node = queue.poll();
        curLevel = levelMap.get(node);
        if(node.left!=null){
            queue.offer(node.left);
            levelMap.put(node.left, curLevel+1);
        }
        if(node.right!=null){
            queue.offer(node.right);
            levelMap.put(node.right, curLevel+1);
        }
    }
    // 检查最后一层的节点，哈希表的size就是总共的节点数
    int num = levelMap.size();
    System.out.println(curLevel);
    return num == (1 << curLevel) - 1;
}

4.5 验证完全二叉树

方法一: 判定节点
定义: 完全二叉树是满树，或正在依次变成满树
判定条件如下:

1. 层次遍历每个节点，如果遇到第一个"孩子不双全的节点",后序的节点都必须是叶节点
2. 遍历的每个节点，不能是"有右无左"，不然立刻判定false

伪代码:
不双全节点标志位:
当left!=null && right==null 时，leaf_flag = true
遇到左空右有的节点:
left==null && right!=null
遇到不全节点后，必须是叶子结点
leaf && !(left==null && right==null)

public static boolean isCompTree_1 (Node root){
    // 层次遍历
    if(root==null){
        return false;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    boolean isLeaf = false;
    while(!queue.isEmpty()){
        Node node = queue.poll();
        // 遇到孩子不完全的结点后，所有的后序节点必须是叶子结点
        // 遇到左空右有的节点，直接返回 false
        if( ( isLeaf && !(node.left==null&&node.right==null)) || (node.left==null && node.right!=null)){
            return false;
        }
        if(node.left!=null){
            queue.offer(node.left);
        }
        if(node.right!=null){
            queue.offer(node.right);
        }
        // 判断叶子结点，遇到不双全的节点
        if( node.left!=null && node.right==null){
            isLeaf = true;
        }
    }
    return true;
}

5. 非递归的前中后序遍历

非递归遍历是进阶遍历的一种

5.1 先序

准备一个栈
初始化：root入栈

1. 出栈cur并打印
2. 检查cur的左右子树，如果有，先右子树，再左子树的入栈
3. 重复1和2，直到栈为空

代码:

// 1. 非递归先序遍历
/*
额外空间： 新建一个栈
时间复杂度：O(n)
初始化：将root压入栈
1. 将cur弹出栈，并打印
2. 如果cur的左右子树存在，先压入右，再压入左[弹出的时候就是：先左后右]
3. 重复1，2直到栈为空
*/
public static void preOrderUnRecur(Node head){
    // 新建一个自己的栈，先压入头节点
    System.out.print("Pre-order: ");
    if(head==null){
        return;
    }
    Stack<Node> stack = new Stack<Node>();
    stack.push(head);
    // 只要栈不为空，就压入栈顶的左右孩子(如果有), 然后再弹出栈顶
    while(!stack.isEmpty()){
        head = stack.pop();
        System.out.print(head.value + " ");
        // 先压入右孩子
        if(head.right!=null){
            stack.push(head.right);
        }
        // 再压入左孩子
        if(head.left!=null){
            stack.push(head.left);
        }
    }
    System.out.println();
}

5.2 中序

额外空间：一个栈
时间复杂度： o(n)
初始化：node!=NULL

1. 把树的左边界压入栈中[若cur的左子树存在，不停的压入，更新cur=cur.left]，直到最后的左叶子停止，转到步骤2；
2. 弹出cur，打印，cur更新为cur->right[检查右子树]，若不为空，重复步骤1，若为空，重复步骤2；
3. 直到stack为空，结束

public static void inOrderUnRecur(Node head){
    // 中序遍历的终止条件特殊，当栈里没有元素时，可能只是把所有的左子树弹出了，还有右子树没有添加
    // 真正的停止条件是: stack为空，且 要添加的右子树为空
    System.out.print("In-order: ");
    if(head==null){
        return;
    }
    Stack<Node> stack = new Stack<Node>();
    while(!stack.isEmpty() || head!=null){
        // 一直添加左子树
        if(head!=null){
            stack.push(head);
            head = head.left;
        }
        // 若head为空，则已经添加到最左边了，检查这个节点
        // 先弹出这个节点，因为它的左子树已经遍历结束了
        // 对右子树也进行，左遍历，分两个情况: 
        // 1. 右子树为空，弹出栈中祖父节点(head作为该祖父节点的左子树已经全部处理完了)
        // 2. 右子树不为空，重复之前的左遍历
        else{
            head = stack.pop();
            System.out.print(head.value + " ");
            head = head.right;
        }
    }
    System.out.println();
}

5.3 后序

额外空间：两个栈
时间复杂度： o(n)
初始化：stack1压入root
思路：模仿PreOrder的顺序，它弹出顺序[中-左-右]，要对其修改

1. stack1弹出cur，不打印，stack2收集弹出的元素
2. 若cur的左右子树存在，先压入左子树，再压入右子树[弹出顺序：中-右-左]
3. 重复过程1，2，直到stack1为空
4. 从栈顶依次弹出stack2的所有元素[相对弹出左-右-中]

public static void postOrderUnRecur(Node head){
    // 参考先序遍历的 根左右 
    // 后序遍历遍历是 左右根，因此先弄出 根右左 用一个栈接住再依次输出
    System.out.print("Post-order: ");
    if(head==null){
        return;
    }
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();

    s1.add(head);
    while (!s1.isEmpty()) {
        // s1 弹出
        head = s1.pop();
        // s2 接住
        s2.push(head);
        // 注意添加顺序，先left再right
        if(head.left!=null){
            s1.push(head.left);
        }
        if(head.right!=null){
            s1.push(head.right);
        }
    }
    while(!s2.isEmpty()){
        head = s2.pop();
        System.out.print(head.value + " ");
    }
    System.out.println();
}

6. 层次输出打印

示例：
二叉树

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：
[ [3],[9,20],[15,7] ]
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)
解法:
每次迭代，都可以把整层节点进行操作，这个操作包括:入list 和 添加左右孩子到队列中

1. 首先根元素入队
2. 当队列不为空的时候
   求当前队列的长度 length
   依次从队列中取length个元素进行操作，然后进入下一次迭代

public List<List<Integer>> levelOrder(TreeNode root) {
    TreeNode node = root;
    List<List<Integer>> lists = new LinkedList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if(root==null){
        return lists;
    }
    queue.offer(node);
    // 层次遍历
    while(!queue.isEmpty()){
        int size = queue.size();
        List<Integer> list = new LinkedList<>();
        // 一次性压入整层节点
        for(int i=0; i<size; i++){
            node = queue.poll();
            list.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        lists.add(list);
    }
return lists;
}