二叉树的相关操作

发表于 | 分类于 | 阅读次数：

     本篇文章包含二叉树的相关操作：前，中，后序遍历（递归和迭代）的实现；二叉树的序列化和反序列化；根据前序和中序遍历还原二叉树；根据中序和后序遍历还原二叉树；

二叉树的遍历

前序遍历（根->左->右）

递归法

1
2
3
4
5
6
7
8
9
10
11
private List<Integer> preorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    preorderHelper(root, res);
    return res;
}
private void preorderHelper(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);
    if (root.left != null) preorderHelper(root.left, res);
    if (root.right != null) preorderHelper(root.right, res);
}

迭代法
算法思想：
（1）先将根节点插入栈中。
（2）若栈不为空，则将栈定元素出栈node。
（3）将node的值插入列表尾；若node.left!=null，则将左节点压入栈；若node.right!=null，则将右节点压入栈。递归至栈为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
private List<Integer> preorderIteration(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root==null) return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()){
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right!=null) stack.push(node.right);
        if (node.left!=null) stack.push(node.left);
    }
    return res;
}
中序遍历（左->根->右）

递归法

1
2
3
4
5
6
7
8
9
10
11
private List<Integer> inorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    inorderHelper(root, res);
    return res;
}
private void inorderHelper(TreeNode root, List<Integer> res) {
    if (root == null) return;
    if (root.left != null) inorderHelper(root.left, res);
    res.add(root.val);
    if (root.right != null) inorderHelper(root.right, res);
}

迭代法
算法思想：
（1）先将根节点插入栈中。
（2）循环将左节点都压入栈，将栈顶元素出栈node，并将其值插入到列表尾。
（3）若当前节点node的右节点node.right不为空，这将其压入栈，并将root指向node.right，并循环执行(2)(3)至栈为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private List<Integer> inorderIteration(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        while (root.left != null) {
            stack.push(root.left);
            root = root.left;
        }
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
            root = node.right;
        }
    }
    return res;
}
后序遍历 (左->右->根)

递归法

1
2
3
4
5
6
7
8
9
10
11
12
private List<Integer> postorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    postorderHelper(root, res);
    return res;
}

private void postorderHelper(TreeNode root, List<Integer> res) {
    if (root == null) return;
    if (root.left != null) postorderHelper(root.left, res);
    if (root.right != null) postorderHelper(root.right, res);
    res.add(root.val);
}

迭代法
算法思想：
（1）先将根节点插入栈中。
（2）若栈不为空，则将栈定元素出栈node。
（3）若node.left!=null，则将左节点压入栈；若node.right!=null，则将右节点压入栈。并将node的值插入列表首。递归至栈为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
private List<Integer> postorderIteration(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
        res.add(0, node.val);
    }
    return res;
}

层序遍历

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            temp.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(temp);
    }
    return res;
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> levelOrderDFS(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    levelOrderHelper(root, 0, res);
    return res;
}
private void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> res) {
    if (root == null) return;
    if (depth + 1 > res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(depth).add(root.val);
    if (root.left != null) levelOrderHelper(root.left, depth + 1, res);
    if (root.right != null) levelOrderHelper(root.right, depth + 1, res);
}

二叉树的序列化和反序列化

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
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    if (root == null) {
        return "[]";
    }
    Queue<String> res = new LinkedList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    res.offer(String.valueOf(root.val));
    while(!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // 有左节点就插入左节点，没有就插入null
        if (node.left != null) {
            queue.offer(node.left);
            res.offer(String.valueOf(node.left.val));
        } else {
            res.offer("null");
        }
        // 有右节点就插入右节点，没有就插入null
        if (node.right != null) {
            queue.offer(node.right);
            res.offer(String.valueOf(node.right.val));
        } else {
            res.offer("null");
        }
    }
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    while(!res.isEmpty()) {
        sb.append(res.poll());
        if (!res.isEmpty()) {
            sb.append(",");
        }
    }
    sb.append("]");
    return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    data = data.substring(1, data.length()-1);
    if (data.length() == 0) {
        return null;
    }
    Queue<String> ls = new LinkedList<>(Arrays.asList(data.split(",")));
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root = null;
    while(!ls.isEmpty()) {
        String res = ls.poll();
        // 创建根节点
        if (root == null) {
            root = new TreeNode(Integer.valueOf(res));
            queue.offer(root);
            continue;
        }
        // 注意：ls的长度总是奇数的，所以除了根节点，其余节点创建时可以一次取两个ls中的元素
        TreeNode father = queue.poll();
        // 创建左节点
        if (!res.equals("null")) {
            TreeNode curr = new TreeNode(Integer.valueOf(res));
            father.left = curr;
            queue.offer(curr);
        }
        // 创建右节点
        res = ls.poll();
        if (!res.equals("null")) {
            TreeNode curr = new TreeNode(Integer.valueOf(res));
            father.right = curr;
            queue.offer(curr);
        }
    }
    return root;
}

根据前序遍历和中序遍历还原二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end, HashMap<Integer, Integer> map) {
    if (p_start == p_end) {
        return null;
    }
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    int i_root_index = map.get(root_val);
    int leftNum = i_root_index - i_start;
    root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index, map);
    root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end, map);
    return root;
}

public TreeNode bstFromPreorder(int[] preorder, int[] inorder) {
    HashMap<Integer,Integer> map = new HashMap<>();
    int idx = 0;
    for (Integer val : inorder)
        map.put(val, idx++);
    return buildTreeHelper(preorder,0,preorder.length,inorder, 0, inorder.length,map);
}

根据后序遍历和中序遍历还原二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static TreeNode dfsPostOrder(int[] inorder, int[] postorder) {
    Map<Integer, Integer> map = new HashMap<>();
    int idx = 0;
    for (int i : inorder) {
        map.put(i, idx++);
    }
    return BuildTreeHelper(inorder, 0, inorder.length, postorder, 0, postorder.length, map);
}

private static TreeNode BuildTreeHelper(int[] inorder, int i_start, int i_end, int[] postorder, int p_start, int p_end, Map<Integer, Integer> map) {
    if (p_start == p_end) return null;
    int root_val = postorder[p_end - 1];
    TreeNode root = new TreeNode(root_val);
    int i_root_index = map.get(root_val);
    int leftNum = i_root_index - i_start;
    root.left = BuildTreeHelper(inorder, i_start, i_root_index,postorder, p_start, p_start + leftNum, map);
    root.right = BuildTreeHelper(inorder, i_root_index + 1, i_end,postorder, p_start + leftNum, p_end - 1, map);
    return root;
}