二叉树的前序遍历、中序遍历、后序遍历--Java、力扣

系统管理员 2023-07-19 05:55 2阅读 0赞

## 二叉树的前序遍历、中序遍历、后序遍历–Java递归解法 ##

**前序遍历代码如下：**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
    //前序遍历
        public List<Integer> preorderTraversal(TreeNode root) {
        
            if(root == null){
        
                return new ArrayList<>();
            }
            List<Integer> left = preorderTraversal(root.left);
            List<Integer> right = preorderTraversal(root.right);
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            list.addAll(left);
            list.addAll(right);
            return list;
    
        }
    }

//前序遍历
        public static void preOrderTraversal(Node root){
        
            if(root == null){
        
                return;
            }
            System.out.println(root);
            preOrderTraversal(root.left);
            preOrderTraversal(root.right);
        }

中序遍历代码如下：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            if(root == null){
        
                return new ArrayList<>();
            }
    
            List<Integer> left = inorderTraversal(root.left);
            List<Integer> right = inorderTraversal(root.right);
            List<Integer> list = new ArrayList<>();
            list.addAll(left);
            list.add(root.val);
            list.addAll(right);
            return list;
        }
    }

//中序遍历
        public static void inOrderTraversal(Node root){
        
            if(root == null){
        
                return;
            }
            inOrderTraversal(root.left);
            System.out.println(root);
            inOrderTraversal(root.right);
        }

后序遍历如下：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            if(root == null){
        
                return new ArrayList<>();
            }
            List<Integer> left = postorderTraversal(root.left);
            List<Integer> right = postorderTraversal(root.right);
            List<Integer> list = new ArrayList<>();
            list.addAll(left);
            list.addAll(right);
            list.add(root.val);
            return list;
        }
    }

//后序遍历
        public static void postOrderTraversal(Node root){
        
            if(root == null){
        
                return;
            }
            postOrderTraversal(root.left);
            System.out.println(root);
            postOrderTraversal(root.right);
        }