树的前序中序后序遍历java代码

  • Post author:
  • Post category:java




前文

本人是通过leedcode学习数据结构的,边学边练,因此大部分题目也都来源于leedcode

今天贴上的是最简单的树遍历的java代码,其实代码部分都是相似的,先创建一个result(list)来存放结果,通过不同遍历方式去安排结点的遍历与数据存放的顺序.


  1. 前序遍历

    :中——左——右
/**
 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两个方法
    }
}

  1. 中序遍历

    :左——中——右

    开头部分的代码与前序相同,后面就不再写上去了,贴主要的代码部分
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);
        
    }
}

  1. 后序遍历

    :左——右——中
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 版权协议,转载请附上原文出处链接和本声明。