力扣剑指offer——二叉树篇

前言

大家好！好久不见我是青花瓷，今天你刷题了吗？文章目录,从易到难,层层递进,本期是结合牛客101和剑指offer上面的二叉树系列OJ面试题,一起学习,一起进步。如果题解对你有帮助,点点赞支持一下,如果有错误的地方,欢迎指正
系列文章推荐:：
1.二叉树基本操作
2.二叉树的前中后序遍历（递归和迭代）
3.【Java数据结构】二叉树丶二叉树进阶——大厂经典OJ面试题——刷题笔记+做题思路

---

二叉树刷题合集

打印二叉树

---

剑指 Offer 32 - I. 从上到下打印二叉树

OJ链接：从上到下打印二叉树

题目描述：

解题思路：

首先读懂题意，这道题就是一个 层序遍历二叉树，但是需要返回到一个数组中。

具体步骤：

1. 借用 顺序表 用来存储二叉树的每个节点的值
2. 借用 辅助队列 来完成二叉树的层序遍历操作
3. 遍历 顺序表，将顺序表的中每个节点的 值返回到 数组中

代码如下：

class Solution {
    public int[] levelOrder(TreeNode root) {
        //层序遍历 一个队列 一个顺序表
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        // 如果头节点为空 返回一个 新的数组
        if(root == null) return new int[0];
        // 如果不为空 将元素 放入 队列中
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            list.add(cur.val);
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
        }
        int[] ret = new int[list.size()];
        for(int i = 0;i < list.size();i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}

---

剑指 Offer 32 - II. 从上到下打印二叉树 II

OJ链接：从上到下打印二叉树 II

题目描述：

解题思路：这道题和上一道题思路一致，只是这道题返回的是一个二维数组，简单的来说，就是在原来的一维数组上，再嵌套了一层数组，这道题需要注意几个细节，如下：

1. 层序遍历 少不了 辅助 队列
2. 返回二维数组，我们需要一个 二维数组接收 返回值
3. 需要用 一个一维数组先去接收每一层节点的值，这里需要注意，接收每一层节点的值，需要放入循环中，确保每一层值的个数
4. 具体，看代码，详细注解

代码如下：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 层序遍历 少不了 辅助 队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 返回的是二位数组
        List<List<Integer>> ret = new ArrayList<>();
        // 一样的，先判断头节点是否为空
        if(root == null) return ret;
        // 不为空 root 如队列
        queue.add(root);
        // 循环条件
        while(!queue.isEmpty()) {
            // 因为我们返回的是一个二维数组，这里我们先用一维数组接收每个节点的值
            List<Integer> list = new ArrayList<>();
            // 这里我们要保证，每个一维数组的值，这里我们需要套上一层循环
            for(int i = queue.size();i > 0;i--) {
            // 弹出 队列 头部 元素,用 cur 接收
            TreeNode cur =  queue.poll();
            list.add(cur.val);
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }   
          }
          // 循环一次，放入一次
            ret.add(list);
        }
        // 最后返回二维数组
        return ret;
    }
}

---

剑指 Offer 32 - III. 从上到下打印二叉树 III

OJ链接：从上到下打印二叉树 III

题目描述：

解题思路：

和上题思路一致，但是这道题说的是，偶数层，反着打印，这里我们需要做如下处理：

因为我们 返回的是 ret ，二维数组，所以，我们用 ret 的大小 去 % 2 ，如果 == 0 ，说明 是偶数层，反之，这里我们 用 双端队列来接收 每层的 节点值

代码如下：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 这道题和上一道题思路一样，只不过这里需要注意：
        // 偶数层需要反着打印
        // 这里难点就在于：反着打印是如何打印的，这里只需要在上一道题原有的基础上
        // 加上一个 判断 if(ret % 2 == 0) 说明是偶数，那么就反着打印
        // 这里反着打印，我们直接用双端队列的性质，双端队列底层是 LinekdList，链表
        // 这里 头插 addLast 尾插 addFirst

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        // 如果 root == null 返回 ret
        if(root == null) return ret;
        // 不为空 如队列
        queue.add(root);
        // 进入循环
        while(!queue.isEmpty()) {
            // 用 List 来接收 每层 节点的值
            LinkedList<Integer> tmp = new LinkedList<>();
            // 这里不同层数，list 接收的 节点数不同，所以我们进入循环
            for(int i = queue.size();i > 0;i--) {
                TreeNode cur = queue.poll();
                // 加入判断,判断是 奇数层 还是 偶数层
                if(ret.size() % 2 == 0) { // 说明是偶数层,反着打印，头插
                    tmp.addLast(cur.val);
                }else {
                    tmp.addFirst(cur.val);
                }
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            ret.add(tmp);
        }
        return ret;
    }
}

---

搜索与回溯算法

剑指 Offer 26. 树的子结构

OJ链接：树的子结构

题目描述：

解题思路&&代码如下：

 // 这道题，主要还是运用了二叉树递归的性质
 // 题意给出：如果 B 是 A 的 子结构，表示 A 中有出现和B 相同结构和节点值

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 边界条件： 如果 A 或者 B 其中一个为空，直接返回 false;
        // 因为题上给出，空数不是任意一个数的子结构
        if(A == null || B == null) return false;

        // 判断完边界，接下来分以下几种情况
        // A 和 B 的根节点相同，依次比较它们的子节点
        // 1. A 的根节点 和 B 的根节点相同，依次比较它们的子节点
        // 2. A 和 B 的 根节点不同，判断 A的左子树中是否 包含 B 的根节点
        // 3. A 和 B 的 根节点不同，判断 A的右子树中是否 包含 B 的根节点
        return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);

    }

    // 以下方法，实现 A 和 B 根节点相同的情况
    boolean isSub(TreeNode A,TreeNode B) {
        // 1. 如果遍历完 B，说明 B的全部节点都 和 A 的子结构匹配上
        if(B == null) return true;
        // 2. A 中的节点为 null ，B 中的节点 不为空，说明 不匹配
        if(A == null) return false;
        // 3. A 和 B 都不为空，但数值不同，说明不匹配
        if(A.val != B.val) return false;
        // 最后，当前这个点是匹配的，继续递归判断左子树和右子树，是否 分别匹配
        return isSub(A.left,B.left) && isSub(A.right,B.right);
    }
}

---

剑指 Offer 27. 二叉树的镜像

OJ链接：二叉树的镜像

题目描述：

解题思路：

先分析题目给出的 输入和输出，很明显，输入是根据二叉树的层序遍历来的，那么我们看输出，输出的图，是除了根节点以外，每一层节点都反过来了。

读懂题意，这道题就很简单了，具体步骤如下：

1. 层序遍历二叉树
2. 在每次入栈之后，交换左右节点的值
3. 返回 根节点

代码如下：

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 注意 这道题和前面的题不同，这里不需要返回二位数组，一维数组啥的，就正常的遍历就行
        
        if(root == null) return null;
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
            // 交换
            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right= tmp;
        }
        return root;
    }
}

---

剑指 Offer 28. 对称的二叉树

OJ链接：对称的二叉树

题目描述：

解题思路：

根据题意，对称二叉树，具体步骤如下：

1. 如果 头节点为空 返回 true，空数也是对称的
2. 判断 左右子树是否 对称
3. 如何判断左右子树是否对称？具体代码如下

代码如下：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 终止条件 空数也是 对称二叉树
        if(root == null) return true;
        // 如果 root 不等于 空 返回 辅助方法
        return func(root.left,root.right);

    }

    // 创建个方法，判断 左右节点是否对称
    boolean func(TreeNode L,TreeNode R) {
        // 如果 左右节点都为空 返回TRUE
        if(L == null && R == null) return true;
        // 如果 左右节点一个为空，或者 左右节点 不相同
        if(L == null || R == null) return false;
        if(L.val != R.val) return false;
        // 最后递归判断 L.left = R.right L.right = R.left
        return func(L.left, R.right) && func(L.right, R.left);
    }
}

---

搜索与回溯算法

剑指 Offer 34. 二叉树中和为某一值的路径

OJ链接：二叉树中和为某一值的路径

题目描述：

解题思路：

代码如下：

class Solution {
    
    // DFS 深度优先搜索，用 双端队列 保存 路径
    // 返回二维数组
    
    Deque<Integer> path = new LinkedList<>();
    List<List<Integer>> ret = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        DFS(root,target);
        return ret;
    }

    public void DFS(TreeNode root,int target) {
        // 1.如果头节点为null，直接返回
        if(root == null) return;
        // 2.不为null，放入 path 中
        path.add(root.val);
        // 3. target值减去 root.val的值
        target -= root.val;
        // 4. 如果 根节点为空，并且 target == 0，说明走完了，将走完的路径放入 ret 中
        if(root.left == null && root.right == null && target == 0) {
            //  这里不能直接 ret.add(path)，如果这样 ret 会随 path 的变化而变化，
            // 这里的操作是复制了 path
            ret.add(new LinkedList<>(path));
        }
        // 5. 如果都没有满足，继续搜索
        DFS(root.left,target);
        DFS(root.right,target);
        // 6. 如果 加入的值，超出了范围 
        path.pollLast();
    }
}

---

剑指 Offer 36. 二叉搜索树与双向链表

OJ链接：二叉搜索树与双向链表

题目描述：

解题思路&&代码如下：

class Solution {

    // 根据题意得：二叉搜索树，左节点 < 根节点 < 右节点 -》 中序遍历

    Node pre,head;
    
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        DFS(root);
        // 首尾相连
        pre.right = head;
        head.left = pre;
        return head;
    }

    // DFS 搜素每个节点，并将每个节点 相连
    public void DFS(Node cur) {
        if(cur == null) return;
        // 中序遍历
        DFS(cur.left);
        // 这里需要判断一下，如果pre 为空，说明 head，为头节点
        if(pre == null) {
            head = cur;
        }else {
            // 如果不为空,建立链接
            pre.right = cur;
        }
        cur.left = pre;
        pre = cur;
        DFS(cur.right);
    }
}

---

剑指 Offer 54. 二叉搜索树的第k大节点

OJ链接：二叉搜索树的第k大节点

题目描述：

解题思路&&代码如下：

class Solution {
    // 核心思路：二叉搜索树，中序遍历为递增
    // 那么如果我们反着来 就为递减，在加入 计数器，没遍历一个节点计数器++
    // 直到计数器 == k 
    // 用 ret 接收 返回值

    int count;
    int ret;
    public int kthLargest(TreeNode root, int k) {
        DFS(root,k);
        return ret;
    }

    void DFS(TreeNode root,int k) {
        if(root == null) return;
        DFS(root.right,k);
        count++;
        if(count == k) ret = root.val;
        DFS(root.left,k);
    }
}