之前一直对树这种数据结构比较畏惧，感觉很难，就没啃这块骨头🤔。这两天就来啃它！实际上它确实难，但是没有我想象中的那么难😂

1. 为什么要使用树？

对于有序数组，我们知道它查找非常快（二分查找）。但是想要在数组中插入一个数据，我们就需要先找到插入数据的位置，将所有插入位置后的数据都向后移一位，才能完成一个数据的插入。平均需要$n/2$次。很费时，删除数据也是一样的道理。

对于链表，正好和数组相反，它插入和删除数据非常快速，我们只需要修改引用即可，但查找数据只能从链表的头部或尾部开始一个一个查找，这样查找平均也需要$n/2$次。

所以希望有一种数据结构能够同时具有查找快和插入删除快的优点，于是便有了树👍。

2. 树

树是一种抽象数据结构（Abstract Data Type, ADT），用来模拟具有树状结构性质的数据集合。它是由n(n > 0)个节点通过连接它们的边组成的具有层次关系的集合。叫它“树”的原因是这样的结构看起来很像一棵倒挂的树，即它是根在上，叶在下的。

  • 节点：图中的黄色圆圈都表示节点。这棵树中共有8个节点。在Java中，节点一般代表对象。
  • 边：连接节点的线称为边。在Java中，边一般是引用。

树有很多种，像上图就称为多路树（节点的子节点数大于两个）。这里主要先学习二叉树[节点的子节点数小于等于两个]。

3. 树的常用名词

  • 根：树顶端的节点。一棵树只有一个根，从根到其它节点的路径有且只能有一条，否则不能称之为树。
  • 父节点：若一个节点含有子节点，那么称这个节点是子节点的父节点。例如B是D的父节点。
  • 子节点：和父节点是相对的概念，若一个节点有父节点，那么称这个节点是父节点的子节点。例如D是B的子节点。
  • 兄弟节点：具有相同父节点的节点称为兄弟节点。例如D和E是兄弟节点。
  • 叶节点：没有子节点的节点称为叶节点。例如D, E, F, G
  • 子树：每个节点都可以作为子树的根，例如在这棵树中，节点B, D, E组成子树，B是子树的根。
  • 节点的层次：从根开始定义，根为第一层，根的子节点为第二层，依次类推。
  • 深度：对于任意节点n，n的深度是从根到n的唯一路径长。根的深度为0。例如D的深度为2，B的深度为1。
  • 高度：对于任意节点n，n的高度是从n到一个叶节点的最长路径长。叶节点的高度为0。例如B的高度为1，A的高度为2。

4. 二叉树

二叉树的每个节点最多只能有两个子节点。

如果给二叉树加一个条件，可以得到一种二叉搜索树(binary search tree) 的特殊二叉树。

它的条件是这样的：对于它的一个节点，如果节点的左子树不为空，那么它左子树的值都小于该节点；如果节点的右子树不为空，那么它右子树的值都大于该节点。

5. 树的遍历

  • 前序遍历：根节点 -> 左子节点 -> 右子节点
  • 中序遍历：左子节点 -> 根节点 -> 右子节点
  • 后序遍历：左子节点 -> 右子节点 -> 根节点

可以根据箭头方向来记忆

例如上图的二叉搜索树，经过遍历后的结果如下：

前序遍历：5 3 1 4 8 6 10
中序遍历：1 3 4 5 6 8 10
后序遍历：1 4 3 6 10 8 5

我们可以发现几个规律：

  1. 前序遍历得到的序列的第一个元素是树的根节点。
  2. 后续遍历得到的序列的最后一个元素是树的根节点。
  3. 对于二叉搜索树，经过中序遍历得到的序列是一个有序数列！（很重要）

6. 几个关于树的题目

6.1 二叉树的深度

题目描述：输入一棵二叉树，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

这里因为包括根和叶节点，这里要求的树的深度相当于树的层数。

解法：

  1. 递归法

思路：对于一个节点，判断其左右子树的高度，最终返回高度较大的值加1.（终止条件：当节点为null时，返回0）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        int l = TreeDepth(root.left);
        int r = TreeDepth(root.right);
        return (l > r ? l : r) + 1;
    }
}

时间复杂度为$O(n)$，空间复杂度为$O(n)$

  1. 层次遍历

思路：使用队列作为辅助空间。

  • 让节点进入队列。此时记录下队列的长度，这个大小就是树当前层的总节点个数。
  • 遍历这个大小，让节点出队，将节点的左右子节点入队。
  • 循环结束，表示当前层遍历完毕，深度加一。
  • 重复前面这个过程直到队列为空停止。
    这是一个模板算法，牢记！

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
37
38
39
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        int count;
        TreeNode node;
        while (queue.size() != 0) {
            // 当前层总节点个数
            count = queue.size();
            for (int i = 0; i < count; i++) {
                // 队列中节点出队
                node = queue.poll();
                // 将节点的左右子节点入队
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            // 一个循环结束，说明遍历完一层
            depth++;
        }
        return depth;
    }
}

时间复杂度为$O(n)$，二叉树每个节点遍历一次。
空间复杂度为$O(n)$，（最差）。树平衡时，队列最多存储$n/2$个节点。

6.2 二叉树的镜像

题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。

二叉树的镜像定义：

1
2
3
4
5
6
7
8
9
10
11
12
   源二叉树
    8
   /  \
  6   10
 / \  / \
5  7 9 11
镜像二叉树
    8
   /  \
  10   6
 / \  / \
11 9 7  5

解法：

  1. 递归法

思路：对当前节点的左右节点进行互换。接着对当前节点的左节点和右节点进行递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) return ;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

时间复杂度为$O(n)$，二叉树每个节点遍历一次。
空间复杂度为$O(n)$，每个节点都会在递归栈中存一次。

  1. 层次遍历

思路：使用上面学到的层次遍历，对每个节点的左右节点进行左右互换。

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
37
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count;
        TreeNode cur;
        TreeNode temp;
        while (queue.size() != 0) {
            count = queue.size();
            for (int i = 0; i < count; i++) {
                cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                // 交换节点
                temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;
            }
        }
    }
}

时间复杂度为$O(n)$，二叉树每个节点遍历一次。
空间复杂度为$O(n)$，（最差）。树平衡时，队列最多存储$n/2$个节点。

6.3 重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：由于前序遍历的第一个元素即是树的根节点，再通过根节点在中序遍历中划分数组（根节点左边的元素即为左树元素，右边的元素即为右树元素。），重复这个过程，直到遍历完中序遍历序列。

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
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre == null || in == null) return null;
        if (pre.length == 0 || in.length == 0) return null;
        // 创建根节点
        TreeNode root = new TreeNode(pre[0]);
        // 根据根节点划分中序遍历序列，为根节点添加左右子树
        for (int i = 0; i < in.length; i++) {
            if (root.val == in[i]) {
                // 左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return root;
    }
}

同理，根据后序遍历和中序遍历，也能重建一个二叉树。（后序遍历的最后一个元素是根节点。🔑）

6.4 序列化二叉树

题目描述：请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

思路：对于序列化，可以将树遍历一遍，将对应的节点转换为字符串即可；对于反序列化，将每一个节点添加到队列中，为其添加左右子节点，直到队列为空。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder result = new StringBuilder("");
        if (root == null) return result.toString();
        // 层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 添加父节点
        result.append(String.valueOf(root.val) + "!");
        TreeNode temp;
        while (!queue.isEmpty()) {
            // 只添加子节点
            temp = queue.poll();
            if (temp.left != null) {
                result.append(String.valueOf(temp.left.val) + "!");
                queue.offer(temp.left);
            } else {
                result.append("#!");
            }
            if (temp.right != null) {
                result.append(String.valueOf(temp.right.val) + "!");
                queue.offer(temp.right);
            } else {
                result.append("#!");
            }
        }
        return result.toString();
  }
    TreeNode Deserialize(String str) {
       // 注意字符串比较
        if (str.equals("")) return null;
        String[] list = str.split("!");
        // 先建立根节点
        TreeNode root = new TreeNode(Integer.parseInt(list[0]));
        // 使用队列管理需要添加子节点的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode temp;
        // 使用index来遍历list，其中index元素的左右子节点分别为2*index+1, 2*index+2
        int index = 0;
        while (!queue.isEmpty() && index < list.length) {
            temp = queue.poll();
            // 这里注意超界问题，index小于list.length, 但2*index+1不一定小于list.length
            if (2 * index + 1 < list.length && !list[2 * index + 1].equals("#")) {
                temp.left = new TreeNode(Integer.parseInt(list[2 * index + 1]));
                // 添加到队列
                queue.offer(temp.left);
            } else {
                temp.left = null;
            }
            if (2 * index + 2 < list.length && !list[2 * index + 2].equals("#")) {
                temp.right = new TreeNode(Integer.parseInt(list[2 * index + 2]));
                // 添加到队列
                queue.offer(temp.right);
            } else {
                temp.right = null;
            }
            // 增加索引值
            index++;
        }
        return root;
  }
}

6.5 二叉搜索树的后序遍历序列

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes，否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：后序遍历的序列是树的根节点，然后遍历除去根节点的序列，找到第一个大于根节点值的索引，此时索引左边为左子树的元素（均小于根节点），而右边为右子树的元素（应大于根节点）[不满足这一条直接返回false]。最终左索引大于等于右索引返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        return judgeOrder(sequence, 0, sequence.length - 1);
    }
    
    public boolean judgeOrder(int[] sequence, int start, int end) {
        // 结束条件
        if (start >= end) return true;
        // 根节点
        int root = sequence[end];
        // 分割节点索引
        int split = start;
        while (split < end && sequence[split] < root) split++;
        // 判断右子树中是否有不满足条件的情况
        for (int i = split; i < end; i++) {
            if (sequence[i] < root) {
                return false;
            }
        }
        // 注意end - 1，将当前的根节点剔除
        return judgeOrder(sequence, start, split - 1) && judgeOrder(sequence, split, end - 1);
    }
}

6.6 树的子结构

题目描述：输入两颗二叉树A, B，判断B是不是A的子结构。（ps: 我们约定空树不是任意一个树的子结构）

思路：首先我们应该遍历大树（A树），找到节点和小树（B树）的根节点相同，然后递归判断节点下的左右子节点是否相同。直到子树遍历完，说明B是A的子结构；否则不是。

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
37
38
39
40
41
42
43
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root2 == null || root1 == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root1);
        TreeNode temp;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            if (temp.val == root2.val) {
                if (judge(temp, root2)) return true;
            }
            if (temp.left != null) queue.offer(temp.left);
            if (temp.right != null) queue.offer(temp.right);
        }
        return false;
    }
    
    private boolean judge(TreeNode root1, TreeNode root2) {
        // 如果小树递归到空，则一定为大树的子结构
        if (root2 == null) return true;
        // 如果小树不为空而大树为空，则小树不为大树的子结构
        if (root1 == null) return false;
        if (root1.val == root2.val) {
            return judge(root1.left, root2.left) && judge(root1.right, root2.right);
        }
        return false;
    }
}

6.7 二叉树中和为某一值的路径

题目描述：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

思路：首先添加节点到路径中，target减去节点的值，判断target是否等于0且节点是否为叶节点，满足则将路径添加到结果中，否则继续递归左右子节点。递归完成后要将路径的最后一个节点删除（即向后走一步，给兄弟节点腾位置。）

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
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null) return result;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            result.add(new ArrayList<>(path));
        }
        FindPath(root.left, target);
        FindPath(root.right, target);
        path.remove(path.size() - 1);
        return result;
    }
}

6.8 对称的二叉树

题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：下图即为一个对称二叉树。我们需要判断根节点的左右节点是否相等，以及左节点的左子节点与右节点的右子节点是否相等，左节点的右子节点与右节点的左子节点是否相等。

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
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if (pRoot == null) return true;
        return isEquals(pRoot.left, pRoot.right);
    }
    
    boolean isEquals(TreeNode node1, TreeNode node2) {
        // 如果两个节点同时为空，返回true
        if (node1 == null && node2 == null) return true;
        // 如果两个节点不同时为空，返回false
        if (node1 == null || node2 == null) return false;
        // 判断节点值是否相等
        if (node1.val == node2.val) {
            return isEquals(node1.left, node2.right) && isEquals(node1.right, node2.left);
        }
        return false;
    }
}