大家好，又见面了，我是你们的朋友全栈君。
首先我们有这么一颗二叉树：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
}
- 前序遍历：根结点 —> 左子树 —> 右子树（先遍历根节点，然后左右）
这棵树的前序遍历为：ABDEGHCF
代码实现:
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
preorder(root, res);
return res;
}
public void preorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
- 中序遍历：左子树—> 根结点 —> 右子树（在中间遍历根节点）
这棵树的中序遍历为：DBGEHACF
代码实现:
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
- 后序遍历：左子树 —> 右子树 —> 根结点（最后遍历根节点）
这棵树的后序遍历为：DGHEBFCA
代码实现:
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
- 层次遍历：按层次遍历
这棵树的层次遍历为：ABCDEFGH
代码实现
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
//将根节点放入队列中，然后不断遍历队列
queue.add(root);
while(queue.size()>0) {
//获取当前队列的长度，这个长度相当于 当前这一层的节点个数
int size = queue.size();
ArrayList<Integer> tmp = new ArrayList<Integer>();
//将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
//如果节点的左/右子树不为空，也放入队列中
for(int i=0;i<size;++i) {
TreeNode t = queue.remove();
tmp.add(t.val);
if(t.left!=null) {
queue.add(t.left);
}
if(t.right!=null) {
queue.add(t.right);
}
}
//将临时list加入最终返回结果中
res.add(tmp);
}
return res;
}
ps: 所谓的前序、中序、后续，就是对根节点而言的，左右的遍历顺序不变，前序就是根节点最先遍历，然后左右；中序就是把根节点放在中间遍历；后序则是把根节点放在最后遍历。
- 笔试题：已知二叉树前序遍历为：ABDEGHCF，中序遍历为：DBGEHACF，求后序遍历
分析：
- 首先我们由前序遍历可知根节点为A
- 已知根节点为A，由中序遍历可知左子树为DBGEH,右子树为CF
确定这两点后就很容易推算出原来的二叉树的样子了。
我们看到右子树节点为CF，中序遍历也是CF，那么就可以推断出现在的二叉树右边是这个样子：
为什么F不是左子树呢，因为如果F在左边，中序遍历的顺序就变成FC了
由前序遍历AB可以知，A的左子树肯定是B，那么现在的树就是这样的：
再由中序遍历DB可知，D为B的左子树
现在只剩下EGH没确定了
首先我们要确定的是D肯定没有子树，如果有，中序遍历就不会是DB了
由前序遍历可知E节点只能是B的右子树了
，最后由中序遍历GEH可知完整的二叉树为：
推断出整棵树后其他的遍历就都很容易写出来了。
这种题的关键是确定根节点和左右子树。如果是已知后序遍历，也是一样的最后一个就是根节点。
关于我
觉得文章不错请扫码关注我吧
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/132889.html原文链接：https://javaforall.net
