數據結構與算法之二叉樹的序列化和反序列化及判斷一棵樹是否為平衡而二叉樹

---

目錄

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

判斷一棵樹是否為平衡而二叉樹

---

1. 二叉樹的序列化和反序列化

1. 遞歸版本序列化和反序列化

代碼實現

// 先序遍歷版本序列化 public static String serialByPre(Node head) {if (head == null) {return "#!";}String res = head.value + "!";res += serialByPre(head.left);res += serialByPre(head.right);return res;}public static Node reconByPreString(String preStr) {String[] values = preStr.split("!");Queue<String> queue = new LinkedList<String>();for (int i = 0; i != values.length; i++) {queue.offer(values[i]);}return reconPreOrder(queue);}public static Node reconPreOrder(Queue<String> queue) {String value = queue.poll();if (value.equals("#")) {return null;}Node head = new Node(Integer.valueOf(value));head.left = reconPreOrder(queue);head.right = reconPreOrder(queue);return head;}

2. 按層次結構序列化和反序列化

代碼實現

public static String serialByLevel(Node head) {if (head == null) {return "#!";}String res = head.value + "!";Queue<Node> queue = new LinkedList<Node>();queue.offer(head);while (!queue.isEmpty()) {head = queue.poll();if (head.left != null) {res += head.left.value + "!";queue.offer(head.left);} else {res += "#!";}if (head.right != null) {res += head.right.value + "!";queue.offer(head.right);} else {res += "#!";}}return res;}public static Node reconByLevelString(String levelStr) {String[] values = levelStr.split("!");int index = 0;Node head = generateNodeByString(values[index++]);Queue<Node> queue = new LinkedList<Node>();if (head != null) {queue.offer(head);}Node node = null;while (!queue.isEmpty()) {node = queue.poll();node.left = generateNodeByString(values[index++]);node.right = generateNodeByString(values[index++]);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return head;}public static Node generateNodeByString(String val) {if (val.equals("#")) {return null;}return new Node(Integer.valueOf(val));}

---

2. 判斷一棵樹是否為平衡二叉樹

概念：左子樹和右子樹高度不超過1即為平衡二叉樹

public class Code_IsBalancedTree {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static boolean isBalance(Node head) {boolean[] res = new boolean[1];res[0] = true;getHeight(head, 1, res);return res[0];}public static int getHeight(Node head, int level, boolean[] res) {if (head == null) {return level;}int lH = getHeight(head.left, level + 1, res);if (!res[0]) {return level;}int rH = getHeight(head.right, level + 1, res);if (!res[0]) {return level;}if (Math.abs(lH - rH) > 1) {res[0] = false;}return Math.max(lH, rH);}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);head.right.right = new Node(7);System.out.println(isBalance(head));}}

總結

以上是生活随笔為你收集整理的数据结构与算法之二叉树的序列化和反序列化及判断一棵树是否为平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。