二叉树算法系列文章
一、概述
二叉树算法第三部分内容包括以下几个主题：
- 将二叉树转换成为链表
- 判断数组是否为二叉树的后序遍历
- 判断某树是否是另一棵树的子树
- 根据前序和中序序列重建二叉树
二、代码实现
2.1 将二叉树转换成为链表
解决思路
采用后序遍历的思路，先将左右子树转换成链表，再将左右子树的链表通过中间结点连接起来。
代码实现
public class Untitled { static class Tree { int size; Node root; } static class Node { Node parent; Node left; Node right; int value; } static class ListValue { Node header; Node tail; } static void insertNode(Tree tree, int value) { if (tree == null) { return; } Node tNode = tree.root; //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。 Node pNode = null; //新的结点。 Node nNode = new Node(); nNode.value = value; while (tNode != null) { pNode = tNode; if (tNode.value > value) { tNode = tNode.left; } else { tNode = tNode.right; } } nNode.parent = pNode; if (pNode == null) { tree.root = nNode; } else if (pNode.value > value) { pNode.left = nNode; } else { pNode.right = nNode; } tree.size++; } static Tree createBinTree(int p[], int len) { Tree tree = new Tree(); for (int i = 0; i < len; i++) { int value = p[i]; insertNode(tree, value); } return tree; } //采用后序遍历的方式转换成链表。 static ListValue treeToList(Node p) { if (p == null) { return null; } ListValue value = new ListValue(); value.header = p; value.tail = p; //左子树部分的链表。 ListValue leftNode = treeToList(p.left); //右子树部分的链表。 ListValue rightNode = treeToList(p.right); //左子树部分的尾结点作为p的前驱节点，右子树部分的头结点作为p的后继结点。 if (leftNode != null) { leftNode.tail.right = p; p.left = leftNode.tail; value.header = leftNode.header; } if (rightNode != null) { rightNode.header.left = p; p.right = rightNode.header; value.tail = rightNode.tail; } return value; } static void printTreeList(ListValue value) { Node node = value.tail; while (node != null && node.left != null) { System.out.println(node.value); node = node.left; } } public static void main(String[] args) { int p[] = { 3, 5, 6, 1, 2, 4, -1, -3}; Tree tree = createBinTree(p, p.length); ListValue value = treeToList(tree.root); printTreeList(value); }}复制代码 运行结果
654321-1复制代码
2.2 判断数组是否为二叉查找树的后序遍历
问题描述
输入一个整数数组，判断该数组是不是某二叉查找树的后序遍历的结果，假设输入的数组的任意两个数字都互不相同。
解决思路
依据题目的描述我们可以得到关键信息：
- 这棵树为二叉查找树，因此对于任意结点，它的左子树小于该结点，右子树大于该结点，并且左右子树都是二叉查找树。
- 如果是后序遍历，那么对于任意子树，它的根结点是该部分数组的最后一个元素。
代码实现
public class Untitled { static boolean isPostOrderOfTree(int p[], int startIndex, int endIndex) { if (startIndex == endIndex) { return true; } int root = p[endIndex]; int middle = startIndex; //通过根结点将左右子树分开。 while (p[middle] < root && middle < endIndex) { middle++; } //验证右子树是否都比根结点要大。 for (int i = middle; i < endIndex; i++) { if (!(p[i] > root)) { return false; } } //说明该结点没有左子树。 if (middle == startIndex || middle == endIndex) { return isPostOrderOfTree(p, startIndex, endIndex - 1); } else { //先验证左边的数组是否是后序遍历。 boolean left = isPostOrderOfTree(p, startIndex, middle - 1); if (left) { //再验证右边的数组是否是后序遍历。 return isPostOrderOfTree(p, middle, endIndex - 1); } else { return false; } } } public static void main(String[] args) { int p1[] = { 5, 7, 6, 9, 11, 10, 8}; System.out.println("p1 是二叉查找树的后序遍历=" + isPostOrderOfTree(p1, 0, p1.length - 1)); int p2[] = { 7, 10, 8, 9}; System.out.println("p2 是二叉查找树的后序遍历=" + isPostOrderOfTree(p2, 0, p2.length - 1)); }}复制代码 运行结果
>> p1 是二叉查找树的后序遍历=true>> p2 是二叉查找树的后序遍历=false复制代码
2.3 判断某树是否是另一棵树的子树
解决思路
先判断父树和子树的根结点是否相等，如果相等，再比较两棵树是否完全相同，如果根结点不相等，那么再递归比较父树的左子树和子树，以及父树的右子树和子树。
代码实现
public class Untitled { static class Tree { int size; Node root; } static class Node { Node parent; Node left; Node right; int value; } static void insertNode(Tree tree, int value) { if (tree == null) { return; } Node tNode = tree.root; //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。 Node pNode = null; //新的结点。 Node nNode = new Node(); nNode.value = value; while (tNode != null) { pNode = tNode; if (tNode.value > value) { tNode = tNode.left; } else { tNode = tNode.right; } } nNode.parent = pNode; if (pNode == null) { tree.root = nNode; } else if (pNode.value > value) { pNode.left = nNode; } else { pNode.right = nNode; } tree.size++; } static Tree createBinTree(int p[], int len) { Tree tree = new Tree(); for (int i = 0; i < len; i++) { int value = p[i]; insertNode(tree, value); } return tree; } static boolean isSubTree(Node node, Node subNode) { if (node == null || subNode == null) { return false; } boolean result = false; if (node.value == subNode.value) { //如果结点相等，那么比较树是否相等。 result = isTreeEquals(node, subNode); } if (!result && node.left != null) { //是否是左子树的子树。 result = isSubTree(node.left, subNode); } if (!result && node.right != null) { //是否是左子树的子树。 result = isSubTree(node.right, subNode); } return result; } static boolean isTreeEquals(Node node1, Node node2) { if (node1 == null && node2 == null) { return true; } if (node1 == null) { return false; } if (node2 == null) { return false; } if (node1.value != node2.value) { return false; } return isTreeEquals(node1.left, node2.left) && isTreeEquals(node1.right, node2.right); } public static void main(String[] args) { int p1[] = { 3, 5, 6, 1, 2, 4, -1, -3}; Tree tree = createBinTree(p1, p1.length); int p2[] = { 1, 2, -1, -3}; Tree subTree = createBinTree(p2, p2.length); int p3[] = { 1, 2, -1, -3, -5}; Tree subTree2 = createBinTree(p3, p3.length); System.out.println("p2 是 p1 的子树=" + isSubTree(tree.root, subTree.root)); System.out.println("p3 是 p1 的子树=" + isSubTree(tree.root, subTree2.root)); }}复制代码 运行结果
>> p2 是 p1 的子树=true>> p3 是 p1 的子树=false复制代码
2.4 根据先序遍历和中序遍历重建二叉树
解决思路
根据先序遍历的特点，其第一个元素为树的根结点，然后在中序遍历的结点中找到该根结点，分为左右两个子树部分，递归进行求解。
代码实现
public class Untitled { static class Tree { int size; Node root; } static class Node { Node parent; Node left; Node right; int value; } static Node createTree(int preOrder[], int preStart, int preEnd, int inOrder[], int inStart, int inEnd) { Node node = new Node(); int root = preOrder[preStart]; node.value = root; //如果只有一个元素，那么直接返回即可。 if (preStart == preEnd) { return node; } int rootIndex = inStart; while (rootIndex < inEnd && inOrder[rootIndex] != root) { rootIndex++; } int leftPreOrderEnd = preStart + (rootIndex - inStart); if (rootIndex != inStart) { node.left = createTree(preOrder, preStart + 1, leftPreOrderEnd, inOrder, inStart, rootIndex - 1); } if (rootIndex != inEnd) { node.right = createTree(preOrder, leftPreOrderEnd + 1, preEnd, inOrder, rootIndex + 1, inEnd); } return node; } static void printPreOrder(Node node) { if (node == null) { return; } System.out.println(node.value); printPreOrder(node.left); printPreOrder(node.right); } static void printInOrder(Node node) { if (node == null) { return; } printInOrder(node.left); System.out.println(node.value); printInOrder(node.right); } public static void main(String[] args) { int p1[] = { 1, 2, 4, 7, 3, 5, 6, 8}; int p2[] = { 4, 7, 2, 1, 5, 3, 8, 6}; Node root = createTree(p1, 0, p1.length - 1, p2, 0, p2.length - 1); System.out.println("- 先序遍历 -"); printPreOrder(root); System.out.println("- 中序遍历 -"); printInOrder(root); }}复制代码 运行结果
- 先序遍历 -12473568- 中序遍历 -47215386复制代码