[数据结构与算法]二叉树的构建和遍历

import java.util.ArrayList;

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

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //    前序遍历——递归LC144——二叉树的前序遍历
    ArrayList<Integer> preorderReverse(TreeNode root){
        ArrayList<Integer> result = new ArrayList<>();
        preOrder(root,result);
        return result;
    }
//    递归参数和返回类型
    void preOrder(TreeNode root,ArrayList<Integer> result){
//        递归终止条件
        if (root == null){
            return;
        }
//        递归单层逻辑
        result.add(root.val);
        preOrder(root.left,result);
        preOrder(root.right,result);
    }

    // 中序遍历·递归·LC94_二叉树的中序遍历
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        inorder(root,res);
        return res;
    }

    void inorder(TreeNode root,ArrayList<Integer> list){
        if (root == null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }

    // 后序遍历·递归·LC145_二叉树的后序遍历
    public ArrayList<Integer> postorderTraversal(TreeNode root){
        ArrayList <Integer> res = new ArrayList<>();
        postorder(root,res);
        return res;
    }
    void postorder(TreeNode root,ArrayList<Integer> list){
        if (root == null){
            return;
        }
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);

    }


    public void createTree(int [] nums){
//        创建一个集合保存树的结点
        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        for (int tempdata:nums) {
            treeNodes.add(new TreeNode(tempdata));
        }
//        将第一个节点设为根节点
        root = treeNodes.get(0);
    /*
    * 利用构建完全二叉树的方式构建
    * */
        for (int i = 0; i < treeNodes.size()/2; i++) {
            if ((i*2+1)< treeNodes.size()){
                treeNodes.get(i).setLeft(treeNodes.get(i*2+1));
            }
            if ((i*2+2)< treeNodes.size()){
                treeNodes.get(i).setRight(treeNodes.get(i*2+2));
            }
        }
    }
    

    public static void main(String[] args) {
        int [] nums = {1,2,3,4,5,6,7,8};
        TreeNode treeNode = new TreeNode();
        treeNode.createTree(nums);
        ArrayList<Integer> res1 =treeNode.preorderReverse(treeNode.getRoot());
        ArrayList<Integer> res2 =treeNode.inorderTraversal(treeNode.getRoot());
        ArrayList<Integer> res3 =treeNode.postorderTraversal(treeNode.getRoot());
        System.out.println(res1);
        System.out.println(res2);
        System.out.println(res3);
    }
}

输出结果：

[1, 2, 4, 8, 5, 3, 6, 7]
[8, 4, 2, 5, 1, 6, 3, 7]
[8, 4, 5, 2, 6, 7, 3, 1]