【每日一题】Leetcode 刷题 二叉树-树的遍历 介绍

前序遍历 （根 左 右）

遍历顺序分别为： F B A D C E G I H

中序遍历 （左 根 右）

中序遍历顺序分别为：A B C D E F G H I

后序遍历 （左 右 根）

后序遍历顺序分别为：A C E D B H I G F

代码实现

前序遍历

• 二叉树的前序遍历 代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList();
        preOrder(root,list);
        return list;
    }
    public void preOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
	//main测试
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node2 = null;
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        node.left=node2;
        node.right=node3;
        node.right.left=node4;

        List<Integer> list = new Solution().preorderTraversal(node);
        System.out.println(list);

    }
}

 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

中序遍历

• 二叉树的中序遍历 代码

 public List<Integer> cenorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList();
        cenOrder(root,list);
        return list;
    }
    //中序遍历  左 根 右
    public void cenOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        cenOrder(root.left,list);
        list.add(root.val);
        cenOrder(root.right,list);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node2 = null;
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        node.left=node2;
        node.right=node3;
        node.right.left=node4;

        // List<Integer> list = new Solution().preorderTraversal(node);
        List<Integer> list = new Solution().cenorderTraversal(node);
        System.out.println(list);

    }

后序遍历

• 后序遍历 代码
  

 public List<Integer> houorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList();
        houOrder(root,list);
        return list;
    }
    //中序遍历  左 根 右
    public void houOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        houOrder(root.left,list);
        houOrder(root.right,list);
        list.add(root.val);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node2 = null;
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        node.left=node2;
        node.right=node3;
        node.right.left=node4;

        // List<Integer> list = new Solution().preorderTraversal(node);
        // List<Integer> list = new Solution().cenorderTraversal(node);
        List<Integer> list = new Solution().houorderTraversal(node);
        System.out.println(list);

    }
}

完整代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    //前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList();
        preOrder(root,list);
        return list;
    }
    //前序遍历  根 左 右
    public void preOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }

    public List<Integer> cenorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList();
        cenOrder(root,list);
        return list;
    }
    //中序遍历  左 根 右
    public void cenOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        cenOrder(root.left,list);
        list.add(root.val);
        cenOrder(root.right,list);
    }

    public List<Integer> houorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList();
        houOrder(root,list);
        return list;
    }
    //中序遍历  左 根 右
    public void houOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        houOrder(root.left,list);
        houOrder(root.right,list);
        list.add(root.val);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node2 = null;
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        node.left=node2;
        node.right=node3;
        node.right.left=node4;

        List<Integer> list = new Solution().preorderTraversal(node);
        // List<Integer> list = new Solution().cenorderTraversal(node);
        // List<Integer> list = new Solution().houorderTraversal(node);
        System.out.println(list);

    }
}

 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}