树的学习——前中后序遍历

根节点 左子树 右子树

public List preorderTraversal(TreeNode root){
	List res = new ArrayList();
	preorder(root,res);
	return res;
}
public void preorder(TreeNode root,List res){
	if(root == null){
		return;
	}
	res.add(root.val);
	preorder(root.left,res);
	preorder(root.right,res);
}

左子树 根节点 右子树

左子树 右子树 根节点

1. 已知前序遍历和中序遍历
2. 已知中序遍历和后序遍历

1. 通过前序遍历确定树的根节点
2. 从中序遍历中找到对应的根节点的位置，将树从根节点以下分为左子树和右子树
3. 根据分开的左子树和右子树来分别到前序遍历中找到各自的根节点
4. 再通过在前序遍历中找到的子树的根节点到对应的中序遍历中找到各自的左子树和右子树
5. 如此反复···

第二种通过已知中序遍历和后序遍历方法类似