考试重点,二叉树

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,根据题目要求。
需要返回: 左右子树的高度leftHeightrightHeight
整合信息: 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;
}