在算法的世界里，数据结构千奇百怪，但是从内存的角度讲数据结构只有两种：数组（顺序存储）和链表（链式存储），所以本节中主要描述二叉树的表达和构建的简单概念并汇总一些构建树的问题。
二叉树的表达
使用数组
示例001.png
对于该树的数组描述为[1,2,3,4,5,null,6,null,8]
note:假设父节点的索引为parent，其左节点的索引为2xparent+1，右节点的索引为2xparent+2
使用链表
链表的方式一般是算法直接操作的对象，所以二叉树构建和实现相关的问题一般都是数组和链表之间的转化，如通过数组构建一个根节点对象，通过遍历的结果恢复一个树，以及树之间的比较等等。下面给出树节点的常用结构。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
二叉树的构建
简单的二叉树的构建一般不做算法问题考察，作为基础一定要牢记于心，一定会有利于解决难题。至少能在调试的过程中快速构建一颗树而不至于手忙脚乱。
public static void main(String[] args) {
TreeNode treeNode = createBinaryTree(new Integer[]{1, 2, 3, 4, 5, null, 6, null, 8}, 0);
System.out.println(treeNode);
}
public static TreeNode createBinaryTree(Integer[] arr, int index) {
if (arr == null || arr.length <= index || arr[index] == null) {
return null;
}
TreeNode root = new TreeNode(arr[index]);
root.left = createBinaryTree(arr, index * 2 + 1);
root.right = createBinaryTree(arr, index * 2 + 2);
return root;
}
还原二叉树
LeetCode题目：
通过二叉树的前序和中序重建二叉树
LeetCode1028，从先序遍历还原二叉树
通过前序和后续重建二叉树
由于建树索引容易混乱，编了顺口溜方便记忆。
前后定根中定子，缺中难建唯一树。
中序索引定头尾, 根值左右为子树。
前后之序索引连，偏移之量中序定。
前序定右左位移，后序定左右位移。
//从前序和中序恢复二叉树
private Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
if (inorder == null || inorder.length == 0) {
return null;
}
if (preorder.length != inorder.length) {
throw new IllegalArgumentException("参数错误");
}
int len = preorder.length;
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return doBuildTree(preorder, 0, len - 1, inorder, 0, len - 1);
}
private TreeNode doBuildTree(int[] preorder, int p_left, int p_right, int[] inorder, int i_left, int i_right) {
if (p_left > p_right || i_left > i_right) {
return null;
}
TreeNode root = new TreeNode(preorder[p_left]);
if (p_left == p_right) {
return root;
}
Integer index = map.get(root.val);
root.left = doBuildTree(preorder, p_left + 1, p_left + (index - i_left), inorder, i_left, index - 1);
root.right = doBuildTree(preorder, p_left + (index - i_left) + 1, p_right, inorder, index + 1, i_right);
return root;
}
/**
* 从中序和后序构建二叉树
*
* @param inorder inorder
* @param postorder postorder
* @return node
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0) {
throw new IllegalArgumentException();
}
if (postorder == null || postorder.length == 0) {
throw new IllegalArgumentException();
}
if (inorder.length != postorder.length) {
throw new IllegalArgumentException();
}
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
//闭区间
return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
//中序遍历 inorder = [9,3,15,20,7]
//后序遍历 postorder = [9,15,7,20,3]
private TreeNode buildTreeHelper(int[] inorder, int inorderLeft, int inorderRight, int[] postorder, int postorderLeft, int postorderRight) {
if (inorderLeft > inorderRight || postorderLeft > postorderRight) {
return null;
}
TreeNode root = new TreeNode(postorder[postorderRight]);
if (postorderRight == postorderLeft){
return root;
}
int inorderCurrentIndex = inorderMap.get(root.val);
root.left = buildTreeHelper(inorder, inorderLeft, inorderCurrentIndex - 1, postorder, postorderLeft, postorderLeft + inorderCurrentIndex - inorderLeft - 1);
root.right = buildTreeHelper(inorder, inorderCurrentIndex + 1, inorderRight, postorder, postorderLeft + inorderCurrentIndex - inorderLeft, postorderRight - 1);
return root;
}
关键点：边界、前序首位值是根、找到根后后序分左右子树
构建平衡BST
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return sortedArrayToBSTHelper(nums, 0, nums.length - 1);
}
private TreeNode sortedArrayToBSTHelper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int midIndex = (right + left) / 2;
TreeNode root = new TreeNode(nums[midIndex]);
root.left = sortedArrayToBSTHelper(nums, left, midIndex - 1);
root.right = sortedArrayToBSTHelper(nums, midIndex + 1, right);
return root;
}
还原BST
class Solution {
public void recoverTree(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root);
swap();
}
public void swap() {
int tmp = one.val;
one.val = another.val;
another.val = tmp;
}
TreeNode pre = null;
TreeNode one = null;
TreeNode another = null;
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root.left);
if (pre == null) {
pre = root;
} else if (root.val < pre.val) {
another = root;
if (one == null) {
one = pre;
}
}
pre = root;
inorderTraversal(root.right);
}
}
