当前位置:网站首页>力扣剑指offer——二叉树篇

力扣剑指offer——二叉树篇

2022-07-05 01:36:00 偷偷敲代码的青花瓷

前言

大家好!好久不见我是青花瓷,今天你刷题了吗?文章目录,从易到难,层层递进,本期是结合牛客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);
    }
}
原网站

版权声明
本文为[偷偷敲代码的青花瓷]所创,转载请带上原文链接,感谢
https://blog.csdn.net/Biteht/article/details/125601980