前文
本人是通过leedcode学习数据结构的,边学边练,因此大部分题目也都来源于leedcode
今天贴上的是最简单的树遍历的java代码,其实代码部分都是相似的,先创建一个result(list)来存放结果,通过不同遍历方式去安排结点的遍历与数据存放的顺序.
-
前序遍历
:中——左——右
/**
2. Definition for a binary tree node.
3. public class TreeNode {
4. int val;
5. TreeNode left;
6. TreeNode right;
7. TreeNode() {}
8. TreeNode(int val) { this.val = val; }
9. TreeNode(int val, TreeNode left, TreeNode right) {
10. this.val = val;
11. this.left = left;
12. this.right = right;
13. }
14. }
*/
class Solution {
public List<Integer> result=new ArrayList<Integer>();
public void preorder(TreeNode head){
if(head==null) return;
result.add(head.val);
preorder(head.left);
preorder(head.right);
}
public List<Integer> preorderTraversal(TreeNode root) {
preorder(root);
return result;
//所有执行结束后,回到根节点才会返回,因此需要preorderTraversal和preorder两个方法
}
}
-
中序遍历
:左——中——右
开头部分的代码与前序相同,后面就不再写上去了,贴主要的代码部分
class Solution {
public List<Integer> result=new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inorder(root);
return result;
}
public void inorder(TreeNode head){
if(head==null) return;
inorder(head.left);
result.add(head.val);
inorder(head.right);
}
}
-
后序遍历
:左——右——中
class Solution {
public List<Integer> result=new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
postorder(root);
return result;
}
public void postorder(TreeNode head){
if(head==null)return;
postorder(head.left);
postorder(head.right);
result.add(head.val);
}
}
总结
不论是前序中序还是后序,思路都是一样的,都是
1.创建一个result列表来保存数据
2.构造返回根节点的方法
3.构造前序/中序/后序搜索的方法,在该方法中先判断该结点是否存在,之后注意result.add的位置就可以了
版权声明:本文为weixin_43387984原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。