剑指offer-树专题总结

---

---

前言

• 主要一些解决方案
  • 1、深度优先搜索
    （大部分使用递归的方式完成，主要要考虑题目是在前序、中序、后序的哪个位置进行。掌握好递归的细节-递归学习链接）
  • 2、广度优先搜索（直接使用队列完成广度优先搜索）

LeetCode-剑指offer专题-树专题如下图

用题说话

（一）递归-DFS

剑指 Offer 07. 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

题目思路

• 1、二叉树的理论中，同时有前序和中序两个遍历的结果时就能确定唯一一颗树
• 2、在前序遍历中你可以找到根节点（就是前序遍历的第一个）
• 3、当你在前序遍历中确定了一个根节点的时候，那么你就可以在中序遍历中定位到该节点
• 4、那么这个节点的左边就是左子树，右边就是右子树
• 5、那么以此类推就可以形成一个递归算法

代码和注释（录一个视频）

    /**
        1、递归
        2、使用指针对数组进行划区域
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return help(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    
    public TreeNode help(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight){
        // 递归结束
        if(preLeft >= preorder.length || inLeft >= inorder.length || preLeft > preRight || inLeft > inRight){
            return null;
        }
        // 每一颗子树他前序遍历的第一个都是该子树的根节点
        int value = preorder[preLeft];
        // 将这个值构建成一颗树节点
        TreeNode node = new TreeNode(value);
        // 由该节点开始划分，计算出左右子树中节点的个数
        int count = inLeft;
        while(inorder[count] != value){
            count ++;
        }
        // count-中序遍历的左指针，这个是按照每轮递归去弄inLeft
        count -= inLeft;
        // 分别构建左右子树
        node.left = help(preorder, inorder, preLeft + 1, preLeft + count,inLeft,inLeft + count - 1);
        node.right = help(preorder, inorder, preLeft + count + 1, preRight, inLeft + count + 1, inRight);

        return node;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

总结（录一个视频）

• 1、中序遍历和前序遍历的特点
  • 前序遍历的第一个节点一定是根节点
  • 每一个根节点在他的中序遍历里面左边和右边分别是左子树和右子树
• 2、递归（递归一直是一个比较难理解的东西）
• 本题理解：这个是一个构建二叉树的递归函数
• 分别构建每一个节点的左右子树
  • 递归三大步（1）：结束条件（划分的范围的左右指针不在理论值范围中时）
  • 递归三大步（2）：返回给上一层递归的东西是what（最后返回null节点）
  • 递归三大步（3）：每轮要干什么（每轮要干的事就是构建左右节点）

剑指 Offer 26. 树的子结构

题目描述

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

题目思路

• 1、想到第一个点，一定是去读这两颗树，判断节点是不是一样
• 2、那么我们可以以使用递归的方式
• 3、再就会想到，子树的位置可能在根节点 | | 左子树某个节点 | | 右子树某个节点
• 4、递归去判断值

代码和注释（录一个视频）

public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 极端情况判断
        if(A == null || B == null){
            return false;
        }

        // 这里分别是三种情况，b的根节点刚好在a的根节点，b的根节点在a的左子树，b的根节点在a的右子树
        return help(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    // 递归函数
    public boolean help(TreeNode A, TreeNode B){
        // 子树完全遍历完成返回true
        if( B == null){
            return true;
        }
        // a所有的子树都遍历完成了，b还有那么一定不是子结构了
        if(A == null){
            return false;
        }
        // 当子树的每个值相同，并且每个b子树对a的子树的节点
        return A.val == B.val && help(A.left, B.left) && help(A.right, B.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结（录一个视频）

• 1、使用的主要方法还是递归
• 2、使用一个子递归进行判断子树的值是否相等
• 3、使用一个大递归去判断左右子树是否有符合的子结构
• 4、递归：
  • 递归三大步（1）：结束条件（有一个是null，子递归null有两种情况）
  • 递归三大步（2）：返回给上一层递归的东西是what（直接返回结果）
  • 递归三大步（3）：每轮要干什么（每轮判断每个节点的值是否相等）

剑指 Offer 27. 二叉树的镜像

题目描述

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

题目思路

1、就是将左边的挂到右边

代码合注释

 // 使用递归，将左右子树进行交换位置
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        // 在递归中交换位置
        // 零时节点：每轮压栈的是当前的left
        TreeNode tempNode = root.left;
        root.left = mirrorTree(root.right);
        // 那这里就是上面的当前栈里的temp
        root.right = mirrorTree(tempNode);

        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结（录一个视频）

这题主要还是递归的思路

（二）广度优先搜索

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

题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

代码思路

1、题目为层级遍历
2、使用广度优先搜索的方式
3、使用到队列先进后出的特性完成

代码和注释（录一个视频）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 使用队列完成广度优先搜索
    public int[] levelOrder(TreeNode root) {
        // 极端判断
        if(root == null){
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> list = new ArrayList<>();
        // 把整颗树先放到队列中
        queue.add(root);
        // 只要队列中还有只就一直迭代
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        return list.stream().mapToInt(Integer::)


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

总结

1、对于这种层级遍历的题目使用广度优先搜索的方式进行
2、我们可以借助队列来完成（先进先出）
3、判断队列是否为空进行迭代