大家好,又见面了,我是你们的朋友全栈君。
首先我们有这么一颗二叉树:
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可知完整的二叉树为:
推断出整棵树后其他的遍历就都很容易写出来了。
这种题的关键是确定根节点和左右子树。如果是已知后序遍历,也是一样的最后一个就是根节点。
关于我
觉得文章不错请扫码关注我吧
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/132889.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...