NC45 实现二叉树先序，中序和后序遍历（递归）

青旅半醒 2022-08-28 04:54 109阅读 0赞

昨天做了NC161 二叉树的中序遍历  
用到的是递归方式（可以背熟），用ArrayList来记录结果，最后再转成一维数组输出就行

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     *   public TreeNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @return int整型一维数组
         */
        public int[] inorderTraversal (TreeNode root) {
        
            // write code here
            List<Integer> list = new ArrayList<Integer>();
            inorder(root,list);
            int[] ans=new int[list.size()];
            for(int i=0;i<list.size();i++){
        
                ans[i]=list.get(i);
            }
            return ans;    
        }
        
        public void inorder(TreeNode root,List<Integer> list){
        
            if(root==null) return;
            inorder(root.left,list);
            list.add(root.val);
            inorder(root.right,list);
        }
    }

这道NC45 实现二叉树先序，中序和后序遍历和上面那题框架是一样的，同样是用递归实现。只是要把一维数组改为二维数组，存放三种遍历的结果

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param root TreeNode类 the root of binary tree
         * @return int整型二维数组
         */
        public int[][] threeOrders (TreeNode root) {
        
            // write code here
            ArrayList<Integer> pre = new ArrayList<Integer>();
            ArrayList<Integer> in = new ArrayList<Integer>();
            ArrayList<Integer> post = new ArrayList<Integer>();
            preOrders(root,pre);
            inOrders(root,in);
            postOrders(root,post);
            int len=pre.size();
            int[][] ans=new int[3][len]; // 创建3行len列的数组存放结果        
            for(int i=0;i<len;i++){
        
                ans[0][i]=pre.get(i);
                ans[1][i]=in.get(i);
                ans[2][i]=post.get(i);                        
            }
            return ans;
        }
        // 先序遍历：根--左--右
        public void preOrders(TreeNode root, ArrayList pre){
        
            if(root==null) return;
            pre.add(root.val);
            preOrders(root.left,pre);
            preOrders(root.right,pre);              
        }
        
       // 中序遍历：左--根--右
        public void inOrders(TreeNode root, ArrayList in){
        
            if(root==null) return;
            inOrders(root.left,in);
            in.add(root.val);        
            inOrders(root.right,in);              
        }
        
        // 后序遍历：左--右--根
        public void postOrders(TreeNode root, ArrayList post){
        
            if(root==null) return;        
            postOrders(root.left,post);
            postOrders(root.right,post);   
            post.add(root.val);
        }
    }