剑指offer面试题6 重建二叉树

考察点

树

知识点

链表中每个结点最少有1个指针，最多2个(双重链表)，前后结点是一对一的关系，而树中每个结点指针数量可以更多一些，也就是说树中的结点存储着更多其它结点的信息，前后结点是一对多的关系(其中靠前的结点有个专门的术语叫父结点，靠后的结点都是孩子结点，没有孩子结点的叫叶子结点，没有父结点的叫根结点)。这俩个数据结构需要解决的问题不一样。依据每个结点包含的指针数量的不同对树做了一些分类，比如每个结点最多包含俩个指针的树叫做二叉树(这里又给这些结点起了个名字二叉树中偏左的叫左结点偏右的叫右结点)
同其它类型的数据结构有一样，树的操作也无外乎创建结点，删除结点，遍历结点，其中创建和删除的过程又都需要用到遍历，遍历一颗普通的树需要O(n)，遍历的方式包括前序遍历(根结点－左结点－右结点)，中序遍历(左结点－根结点－右结点)，后序遍历(左结点－右结点－根结点)，遍历的代码实现包括递归和迭代俩种方式，下面代码中有实现。其实递归就是用了程序自己的栈，迭代是用了我们自己创建的栈。
数据结构的目的肯定是为了更高效的使用数据，基于树的这种结构，如果把比父结点小的数据都存左边，比父结点大的数据都存右边，这样查找数据的时候就有点类似于二分查找了，时间复杂度降到O(logn),这样的树被称作搜索树

题目

分析
本题目输入的一个树的前序和中序遍历序列，要求把这颗树重建起来。这里需要了解到程序中有个特别重要的思维叫递归，递归是分层的，每一层的问题都是一样的，只不过问题的规模不一样，面对这类复杂问题你的思考方式一定是2点：1.问题该如何定义？第n层该如何解决？如果第n层的问题已经解决好了，那么就继续用第n层的方式去解决第n－1层；2.第0层的问题是怎么样的该怎么解决。套到这个题目中问题显然就是用一个前序序列和一个中序序列构建树，(1思维展现)第n层问题怎么解决？前序遍历第一个元素就是根结点，而中序遍历左根右如果能找到根结点在中序序列中的位置，那么就能确定该根结点左边的所有结点都是左子树的中序序列，右边的所有结点都是右子树的中序序列，结点数目知道了以后再返回前序遍历找出左子树的前序序列和右子树的前序序列，这样一来就可以继续用这个方法去分别构建左子树和右子树。(2思维展现)第0层肯定是问题规模最小的那一层，本题目中即只有一个结点的时候，这种情况直接解决本层问题就可以了。

public class Node{
	int val;
	Node leftChild;
	Node rightChild;

	public Node(int data) {
		this.val = data;
		this.leftChild = null;
		this.rightChild = null;
	}
}
import java.util.Deque;
import java.util.LinkedList;

public class BinaryTree {
	Node root;

	public BinaryTree() {
		this.root = null;
	}
	public void insertTree(int val) {
		if (this.root == null) {
			Node root = new Node(val);
			this.root = root;
		} else {
			insertChildTree(this.root,val);
		}
	}
	public void insertChildTree(Node node,int val) {
		if (node != null && val < node.val) {
			if (node.leftChild == null) {
				node.leftChild = new Node(val);
			} else {
				insertChildTree(node.leftChild,val);
			}
		}
		if (node != null && val > node.val) {
			if (node.rightChild == null) {
				node.rightChild = new Node(val);
			} else {
				insertChildTree(node.rightChild,val);
			}
		}
	}
	public Node getRoot() {
		return this.root;
	}
	public void prePrint(Node node) {
		if (node == null) {
			return;
		}
		System.out.print(node.val + " ");
		prePrint(node.leftChild);
		prePrint(node.rightChild);
	}
	public void midPrint(Node node) {
		if (node == null) {
			return;
		}
		midPrint(node.leftChild);
		System.out.print(node.val + " ");
		midPrint(node.rightChild);
	}
	public void afterPrint(Node node) {
		if (node == null) {
			return;
		}
		afterPrint(node.leftChild);
		afterPrint(node.rightChild);
		System.out.print(node.val + " ");
	}
	public void prePrintIteration(Node root) {
		Deque<Node> stack = new LinkedList<>();
		Node node = root;
		while (stack.size() > 0 || node != null) {
			while (node != null) {
				System.out.print(node.val + " ");
				stack.push(node);
				node = node.leftChild;
			}
			if (stack.size() > 0) {
				node = stack.peek().rightChild;
				stack.pop();

			}
		}
	}
	public void midPrintIteration(Node root) {
		Deque<Node> stack = new LinkedList<>();
		Node node = root;
		while (stack.size() > 0 || node != null) {
			while (node != null) {
				stack.push(node);
				node = node.leftChild;
			}
			//执行到此说明左子树都已入栈
			if (stack.size() > 0) {
				Node parent = stack.peek();//父结点
				System.out.print(parent.val + " ");
				node = parent.rightChild;
				stack.pop();
			}
		}
	}
	public void afterPrintIteration(Node root) {
		Deque<Node> stack = new LinkedList<>();
		Node pre = null;
		Node node = root;
		while (stack.size() > 0 || node != null) {
			while (node != null) {
				stack.push(node);
				node = node.leftChild;
			}
			Node parent = stack.peek();
			if (parent.rightChild == pre || parent.rightChild == null) {
				System.out.print(parent.val + " ");
				pre = parent;
				stack.pop();
			} else {
				node = parent.rightChild;
			}
		}
	}
	public void constructPrint(int[] pre,int[] mid) {
		if (pre.length != mid.length || pre.length <= 0) {
			throw new Error("params error");
		}
		int len = pre.length;
		Node root = constructTree(pre,0,len-1,mid,0,len-1);
		prePrint(root);
		System.out.println();
		midPrint(root);
		System.out.println();
	}
	public Node constructTree(int[] pre,int preStart,int preEnd,int[] mid,int midStart,int midEnd) {
		int rootVal = pre[preStart];
		Node root = new Node(rootVal);
		root.leftChild = null;
		root.rightChild = null;
		if (preStart == preEnd && midStart == midEnd) {
			if (pre[preStart] != mid[midStart]) {
				throw new Error("input error");
			} else {
				return root;
			}
		}

		int leftMidEnd = midStart;
		for (int i = midStart;i <= midEnd; i++) {
			if (rootVal != mid[i]) {
				leftMidEnd ++;
			} else {
				break;
			}
		}
		//根结点在中序序列中不存在
		if (leftMidEnd > midEnd) {
			throw new Error("input error");
		}
		int leftLength = leftMidEnd - midStart;
		if (leftLength > 0) {
			root.leftChild = constructTree(pre,preStart + 1,preStart + leftLength,mid,midStart,leftMidEnd - 1);
		}
		if (leftLength < midEnd - midStart) {
			root.rightChild = constructTree(pre,preStart + leftLength + 1,preEnd,mid,leftMidEnd + 1,midEnd);
		}
		return root;
	}
}
public class Six {
	public static void main(String[] args) {
		//树的遍历
		BinaryTree tree = new BinaryTree();
		tree.insertTree(10);
		tree.insertTree(6);
		tree.insertTree(14);
		tree.insertTree(4);
		tree.insertTree(8);
		tree.insertTree(12);
		tree.insertTree(16);
		tree.prePrint(tree.getRoot());
		System.out.println();
		tree.prePrintIteration(tree.getRoot());
		System.out.println();
		tree.midPrint(tree.getRoot());
		System.out.println();
		tree.midPrintIteration(tree.getRoot());
		System.out.println();
		tree.afterPrint(tree.getRoot());
		System.out.println();
		tree.afterPrintIteration(tree.getRoot());
		System.out.println();
		int[] pre = {1,2,4,7,3,5,6,8};
		int[] mid = {4,7,2,1,5,3,8,6};
		／／本题目重建二叉树
		BinaryTree treeBuild = new BinaryTree();
		treeBuild.constructPrint(pre,mid);
	}
}