首页 > 试题广场 >

实现二叉树先序,中序和后序遍历

[编程题]实现二叉树先序,中序和后序遍历
  • 热度指数:170335 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一棵二叉树,分别按照二叉树先序,中序和后序打印所有的节点。

数据范围:,树上每个节点的val值满足 
要求:空间复杂度 ,时间复杂度
样例解释:
如图二叉树结构
示例1

输入

{1,2,3}

输出

[[1,2,3],[2,1,3],[2,3,1]]

说明

如题面图  
示例2

输入

{}

输出

[[],[],[]]

备注:

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution
{
public:
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> threeOrders(TreeNode *root)
    {
        // write code here
        vector<vector<int>> result({{}, {}, {}});
        visit(root, result);
        return result;
        /*
        vector<int> a;
        visit1(root,a);
        result.push_back(a);
        a.clear();
        visit2(root,a);
        result.push_back(a);
        a.clear();
        visit3(root,a);
        result.push_back(a);
        a.clear();
        return result;
        */
    }
    void visit(TreeNode *root, vector<vector<int>> &a)
    {
        if (!root)
            return;
        a[0].push_back(root->val);
        visit(root->left, a);
        a[1].push_back(root->val);
        visit(root->right, a);
        a[2].push_back(root->val);
    }
    /*
    void visit1(TreeNode *root, vector<int> &a)
    {
        if (!root)
            return;

        a.push_back(root->val);
        visit1(root->left, a);
        visit1(root->right, a);
    }
    void visit2(TreeNode *root, vector<int> &a)
    {
        if (!root)
            return;

        visit2(root->left, a);
        a.push_back(root->val);
        visit2(root->right, a);
    }
    void visit3(TreeNode *root, vector<int> &a)
    {
        if (!root)
            return;

        visit3(root->left, a);
        visit3(root->right, a);
        a.push_back(root->val);
    }
    */
};

发表于 2022-02-21 14:50:22 回复(0)
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<int> preOrder(TreeNode* root){
        vector<int> res;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode* cur = s.top();
            s.pop();
            res.push_back(cur->val);
            if(cur->right){
                s.push(cur->right);
            }
            if(cur->left){
                s.push(cur->left);
            }

        }
        return res;
    }
    vector<int> inOrder(TreeNode* root){
        vector<int> res;
        stack<pair<TreeNode*,bool> > s;
        s.push(make_pair(root,true));
        while(!s.empty()){
            TreeNode* cur = s.top().first;
            if(s.top().second && cur->left){
                s.top().second=false;
                s.push(make_pair(cur->left, true));
                continue;
            }
            res.push_back(cur->val);
            s.pop();
            if(cur->right){
                s.push(make_pair(cur->right, true));
            }
        }
        return res;
    }
    
    vector<int> postOrder(TreeNode* root){
        vector<int> res;
        stack<pair<TreeNode*,int> > s;
        s.push(make_pair(root,1));//1为应该push left;2为应该push right;3为应该push_back val
        while(!s.empty()){
            TreeNode* cur = s.top().first;
            if(s.top().second==1){
                s.top().second++;
                if(cur->left){
                    s.push(make_pair(cur->left, 1));
                }
            }else if(s.top().second==2){
                s.top().second++;
                if(cur->right){
                    s.push(make_pair(cur->right, 1));
                }
            }else{
                s.pop();
                res.push_back(cur->val);
            }
        }
        return res;
    }
    
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        vector<vector<int>> result;
        result.push_back(preOrder(root));
        result.push_back(inOrder(root));
        result.push_back(postOrder(root));
        return result;
    }
};
借用栈实现的非递归解法~
发表于 2020-12-28 14:04:52 回复(1)
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<int> v1;
    void MLR(TreeNode* root){
        if(!root)return;
        v1.push_back(root->val);
        MLR(root->left);
        MLR(root->right);
    }
    void LMR(TreeNode* root){
        if(!root)return;
        LMR(root->left);
        v1.push_back(root->val);
        LMR(root->right);
    }
    void LRM(TreeNode* root){
        if(!root)return;
        LRM(root->left);
        LRM(root->right);
        v1.push_back(root->val);
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        //先实现先序遍历
        vector<vector<int> > vv;
        TreeNode* temp=root;
        v1.clear();
        MLR(temp);
        vv.push_back(v1);
        v1.clear();
        LMR(temp);
        vv.push_back(v1);
        v1.clear();
        LRM(temp);
        vv.push_back(v1);
        v1.clear();
        return vv;
    }
};
发表于 2020-08-31 13:34:56 回复(0)
vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int> > ans;
        vector<int> preo,ino,pos;
        stack<TreeNode*> st;
        TreeNode * p=root;
        /*“迭代方法,有点啰嗦“*/
        while(p||!st.empty()){                  //先序
            if(p){
                st.push(p);
                preo.push_back(st.top()->val);
                p=p->left;
                
            }
            else{
                p=st.top();
                st.pop();
                p=p->right;
            }
        }
        ans.push_back(preo);
        TreeNode* q=root;
        while(q||!st.empty()){                  //中序
            if(q){
                st.push(q);
                
                q=q->left;
                
            }
            else{
                
                q=st.top();
                ino.push_back(st.top()->val);
                st.pop();
                q=q->right;
            }
        }
        ans.push_back(ino);
        TreeNode* r=root;
        while(r||!st.empty()){                  //后序
            if(r){
                st.push(r);
                pos.push_back(st.top()->val);
                r=r->right;
                
            }
            else{
                
                r=st.top();
                st.pop();
                r=r->left;
            }
        }
        reverse(pos.begin(),pos.end());
        ans.push_back(pos);
        return ans;
        
        
    }

发表于 2020-09-03 22:27:01 回复(2)
function threeOrders( root ) {
    // write code here
    let arr1 = [];
    let arr2 = [];
    let arr3 = [];
    return [pre(root, arr1), mid(root, arr2), next(root, arr3)];
}
function pre(root, arr1){
    
    if(root ==null) return root;
    arr1.push(root.val)
    pre(root.left, arr1)
    pre(root.right, arr1)
    return arr1
}
function mid(root, arr2){
    if(root ==null) return root;
    mid(root.left, arr2)
    arr2.push(root.val)
    mid(root.right, arr2)
    return arr2
}
function next(root, arr3){
    if(root ==null) return root;
    next(root.left, arr3)
    next(root.right, arr3)
    arr3.push(root.val)
    return arr3
}
module.exports = {
    threeOrders : threeOrders
};
发表于 2021-08-28 16:02:16 回复(0)
递归处理
import java.util.*;
public class Solution {
    List<Integer> pre = new ArrayList<>();
    List<Integer> mid = new ArrayList<>();
    List<Integer> last = new ArrayList<>();
    public int[][] threeOrders (TreeNode root) {
        dfs(root);
        int n = pre.size();
        int[][] res = new int[3][n];
        for(int i=0;i<n;i++){
            res[0][i] = pre.get(i);
            res[1][i] = mid.get(i);
            res[2][i] = last.get(i);
        }
        return res;
    }
    public void dfs(TreeNode root){
        if(root==null) return;
        pre.add(root.val);
        dfs(root.left);
        mid.add(root.val);
        dfs(root.right);
        last.add(root.val);
    }
}


发表于 2021-03-16 10:40:10 回复(0)
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
        int[][] array = new int[3][];
        List<Integer> list1 = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();
        List<Integer> list3 = new ArrayList<Integer>();
        preorder(root, list1);
        inorder(root, list2);
        postorder(root, list3);
        array[0] = new int[list1.size()];
        array[1] = new int[list2.size()];
        array[2] = new int[list3.size()];
        for (int i = 0; i < list1.size(); ++i){
            array[0][i] = list1.get(i);
            array[1][i] = list2.get(i);
            array[2][i] = list3.get(i);
        }
        return array;
    }
    
    public void preorder(TreeNode root, List<Integer> list){
        if (root != null){
            list.add(root.val);
            preorder(root.left, list);
            preorder(root.right, list);
        }
    }
    
    public void inorder(TreeNode root, List<Integer> list){
        if (root != null){
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }
    
    public void postorder(TreeNode root, List<Integer> list){
        if (root != null){
            postorder(root.left, list);
            postorder(root.right, list);
            list.add(root.val);
        }
    }
}

发表于 2021-08-31 19:59:01 回复(0)
Python
遇到树结构一般都可以从递归的思考方向入手
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 the root of binary tree
# @return int整型二维数组
#
class Solution:
    def mlr_dfs(self,root):
        if not root:
            return None
        self.result1.append(root.val)
        self.mlr_dfs(root.left)
        self.mlr_dfs(root.right)
    def lmr_dfs(self,root):
        if not root:
            return None
        self.lmr_dfs(root.left)
        self.result2.append(root.val)
        self.lmr_dfs(root.right)
    def rml_dfs(self,root):
        if not root:
            return None
        self.rml_dfs(root.left)
        self.rml_dfs(root.right)
        self.result3.append(root.val)
    def threeOrders(self , root ):
        # write code here
        result = []
        self.result1 = []
        self.mlr_dfs(root)
        result.append(self.result1)
        self.result2 = []
        self.lmr_dfs(root)
        result.append(self.result2)
        self.result3 = []
        self.rml_dfs(root)
        result.append(self.result3)
        return result
#     简化一下就是评论区的简化版答案
# class Solution:
#     def threeOrders(self , root ):
#         # write code here
#         self.res = [[],[],[]]
#         self.dfs(root)
#         return self.res
        
#     def dfs(self,root):
#         if not root: return
#         self.res[0].append(root.val)
#         self.dfs(root.left)
#         self.res[1].append(root.val)
#         self.dfs(root.right)
#         self.res[2].append(root.val)
#         return



发表于 2021-04-30 15:44:46 回复(2)
个人觉得,代码,越简洁越好,越规律越好
class Solution {
public:
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<int> before;
        vector<int> middle;
        vector<int> after;
        Before(root, before);
        Middle(root,middle);
        After(root, after);
        vector<vector<int>> ans = {before,middle,after};
        return ans;
            
    }
    
    void Before(TreeNode* root,vector<int>& before){
        if(root==nullptr){
            return;
        }
        before.push_back(root->val);
        Before(root->left, before);
        Before(root->right,before);
    }
    
    void Middle(TreeNode* root,vector<int>& before){
        if(root==nullptr){
            return;
        }
        Middle(root->left, before);
        before.push_back(root->val);
        Middle(root->right,before);
    }
    
    void After(TreeNode* root,vector<int>& before){
        if(root==nullptr){
            return;
        }
        After(root->left, before);
        After(root->right,before);
        before.push_back(root->val);
    }
    
    
};


发表于 2021-12-03 17:53:32 回复(0)
这题根本就不是在考察二叉树遍历,大部分时间实际上是在处理怎么把结果装到二维数组里。另外很多答案写了三个子函数,不是很能理解。
public class Solution {
    public int[][] threeOrders (TreeNode root) {        
        int[][]temp = new int[3][0];
        if (root == null) return temp;
        ArrayList<Integer> first = new ArrayList<>();
        ArrayList<Integer> mid = new ArrayList<>();
        ArrayList<Integer> back = new ArrayList<>();
        DFS(root, first, mid, back);
        int[][] res = new int[3][first.size()];
        for (int i = 0; i < first.size(); i++){
            res[0][i] = first.get(i);
            res[1][i] = mid.get(i);
            res[2][i] = back.get(i);
        }
        return res;
    }
    void DFS(TreeNode root, ArrayList<Integer> first, ArrayList<Integer> mid,
             ArrayList<Integer> back){
        if (root == null)
            return;
        first.add(root.val);
        DFS(root.left, first, mid, back);
        mid.add(root.val);
        DFS(root.right, first, mid, back);
        back.add(root.val);
    }
}


发表于 2021-11-18 15:41:35 回复(0)

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    int midIndex = 0;
    int pre = 0;
    int after = 0;
    public int[][] threeOrders (TreeNode root) {
        // write code here
        //根据root节点个数创建int[][]
        int count = 1;
        int length = rootCount(root);
        int[][] result = new int[3][length];
        helper(root,result);
        return result;
    }
    
    public int rootCount(TreeNode root){
        if(root == null){
            return 0;
        }
        return rootCount(root.left) + rootCount(root.right)+1;
    }
    
 
    public void helper(TreeNode root,int[][] result){
        if(root == null){
            return;
        }
        //中
        result[0][pre++] = root.val;
        helper(root.left,result);
        result[1][midIndex++] = root.val;
        helper(root.right,result);
        result[2][after++] = root.val;
    }
}
发表于 2021-08-29 11:48:02 回复(0)
递归处理。第一次遍历之后可以确定节点数,后续遍历可以一次性开辟足够的空间。
enum VisitMode {
    kPre,
    kIn,
    kPost
};

class Solution {
public:
    vector<vector<int>> threeOrders(TreeNode* root) {
        vector<int> pre;
        this->visit(root, VisitMode::kPre, pre);

        vector<int> mid;
        mid.reserve(pre.size());
        this->visit(root, VisitMode::kIn, mid);

        vector<int> post;
        post.reserve(pre.size());
        this->visit(root, VisitMode::kPost, post);

        vector<vector<int>> result;
        result.push_back(pre);
        result.push_back(mid);
        result.push_back(post);
        return result;
    }

    const void visit(const TreeNode* root, const VisitMode mode, vector<int>& result) {
        if (!root) {
            return;
        }
        switch(mode) {
            case VisitMode::kPre:
                result.push_back(root->val);
                this->visit(root->left, mode, result);
                this->visit(root->right, mode, result);
                break;
            case VisitMode::kIn:
                this->visit(root->left, mode, result);
                result.push_back(root->val);
                this->visit(root->right, mode, result);
                break;
            case VisitMode::kPost:
                this->visit(root->left, mode, result);
                this->visit(root->right, mode, result);
                result.push_back(root->val);
                break;
        }
    }
};


发表于 2021-07-25 16:52:38 回复(0)
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    // 递归就不说了
//     void pre(TreeNode* root, vector<int>& rt) {
//         if(!root) {
//             return;
//         }
//         rt.push_back(root->val);
//         pre(root->left, rt);
//         pre(root->right, rt);
//     }
//     void middle(TreeNode* root, vector<int>& rt) {
//         if(!root) {
//             return;
//         }
//         middle(root->left, rt);
//         rt.push_back(root->val);
//         middle(root->right, rt);
//     }
//     void suf(TreeNode* root, vector<int>& rt) {
//         if(!root) {
//             return;
//         }
//         suf(root->left, rt);
//         suf(root->right, rt);
//         rt.push_back(root->val);
//     }
    // 非递归
        vector<vector<int> > threeOrders(TreeNode* root) {
            // write code here
            vector<vector<int>> rt;
            vector<int> pre_rt;
            vector<int> middle_rt;
            vector<int> suf_rt;
            pre(root, pre_rt);
            middle(root, middle_rt);
            suf(root, suf_rt);
            rt.push_back(pre_rt);
            rt.push_back(middle_rt);
            rt.push_back(suf_rt);
            return rt;
        }
        // 前序遍历和中序遍历的唯一区别是:左边深入的时候访问还是,左边深入到头,再慢慢pop出来访问
        void pre(TreeNode* root, vector<int>& rt) {
            if(!root) {
                return;
            }
            stack<TreeNode*> tmp;
            TreeNode* cur = root;
            while (!tmp.empty()||cur) {
                while(cur) { // 个人习惯,喜欢一开始左边走到头
                    rt.push_back(cur->val);
                    tmp.push(cur);
                    cur = cur->left;
                }
                if (!tmp.empty()) {
                    cur = tmp.top();
                    tmp.pop();
                    cur = cur->right;
                }
            }
        }
        void middle(TreeNode* root, vector<int>& rt) {
            if(!root) {
                return;
            }
            stack<TreeNode*> tmp;
            TreeNode* cur = root;
            while (!tmp.empty()||cur) {
                while(cur) { // 个人习惯,喜欢一开始左边走到头
                    tmp.push(cur);
                    cur = cur->left;
                }
                if (!tmp.empty()) {
                    cur = tmp.top();
                    rt.push_back(cur->val);
                    tmp.pop();
                    cur = cur->right;
                }
            }
        }
        void suf(TreeNode* root, vector<int>& rt) {
            if(!root) {
                return;
            }
            stack<TreeNode*> tmp;
            TreeNode* cur = root;
            TreeNode* lastVisit;
            while (!tmp.empty()||cur) {
                while(cur) {  // 个人习惯,喜欢一开始左边走到头
                    tmp.push(cur);
                    cur = cur->left;
                }
                if (!tmp.empty()) {
                    cur = tmp.top();
                    // 访问根节点的条件
                    // 1.无右子树 或 2.右子树已经访问完毕
                    if (!cur->right || lastVisit == cur->right) {
                        rt.push_back(cur->val);
                        lastVisit = cur;
                        tmp.pop();
                        cur = NULL; // 不置为空,则 cur = tmp.top() 又会在下次 while 进入到栈里面,死循环
                    } else {
                        cur = cur->right;
                    }
                }
            }
        }
};

发表于 2021-07-11 19:02:12 回复(0)

递归遍历 + 迭代遍历

class Solution:
    def threeOrders(self, root):
        # return self.recursive(root)
        return self.iterate(root)

    def recursive(self, root: TreeNode):
        self.ans = [[], [], []]
        self.preorder(root)
        self.inorder(root)
        self.postorder(root)
        return self.ans

    def preorder(self, root: TreeNode) -> None:
        if not root:
            return

        self.ans[0].append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)

    def inorder(self, root: TreeNode) -> None:
        if not root:
            return

        self.inorder(root.left)
        self.ans[1].append(root.val)
        self.inorder(root.right)

    def postorder(self, root: TreeNode) -> None:
        if not root:
            return

        self.postorder(root.left)
        self.postorder(root.right)
        self.ans[2].append(root.val)

    def iterate(self, root):
        return [self.preiter(root), self.initer(root), self.postiter(root)]

    def preiter(self, root):
        ans, stk = [], [root]
        while stk:
            root = stk.pop()
            ans.append(root.val)
            if root.right:
                stk.append(root.right)
            if root.left:
                stk.append(root.left)
        return ans

    def initer(self, root):
        ans, stk = [], []
        while root or stk:
            while root:
                stk.append(root)
                root = root.left
            root = stk.pop()
            ans.append(root.val)
            root = root.right
        return ans

    def postiter(self, root):
        ans, stk = [], [root]
        while stk:
            root = stk.pop()
            ans.append(root.val)
            if root.left:
                stk.append(root.left)
            if root.right:
                stk.append(root.right)
        ans.reverse()
        return ans
发表于 2021-04-26 23:04:47 回复(0)
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整型二维数组
     */
    List<Integer> list = new ArrayList<>();
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();
    int i = 0, j = 0, k = 0;
    public int[][] threeOrders (TreeNode root) {
        search(root);
        int[][] end = new int[3][list.size()];
        for(int i = 0; i < list.size(); i++)
            end[0][i] = list.get(i);
        search1(root);
        for(int i = 0; i < list1.size(); i++)
            end[1][i] = list1.get(i);
        search2(root);
            for(int i = 0; i < list2.size(); i++)
            end[2][i] = list2.get(i);
        return end;
        
    }
    public void search(TreeNode root) {
        if(root == null)
            return;
        list.add(root.val);
        search(root.left);
        search(root.right);
    }
        public void search1(TreeNode root) {
        if(root == null)
            return;
        search1(root.left);
             list1.add(root.val);
        search1(root.right);
    }
        public void search2(TreeNode root) {
        if(root == null)
            return;    
        search2(root.left);
        search2(root.right);
         list2.add(root.val);
    }
}

发表于 2021-04-24 21:43:36 回复(0)
使用JS来实现本题,使用的简单的递归方法。
三种遍历的简单实现很容易记,先序就在开头进行业务逻辑操作然后再递归左右子节点,中序就在递归左右子节点之间进行业务逻辑操作,后序就先进行递归然后再进行业务逻辑功能实现。
function first(root,arr){   
    if(root==null) return;
    arr.push(root.val);
    first(root.left,arr);
    first(root.right,arr);
}
function mid(root,arr){    
    if(root==null) return;    
    mid(root.left,arr);
    arr.push(root.val);
    mid(root.right,arr);
}
function back(root,arr){    
    if(root==null) return;    
    back(root.left,arr);    
    back(root.right,arr);
    arr.push(root.val);
}

function threeOrders( root ) {
    // write code here
    let arr1=[],arr2=[],arr3=[];
    let ret=[];
    first(root,arr1)
    mid(root,arr2)
    back(root,arr3)
    ret.push(arr1);
    ret.push(arr2);
    ret.push(arr3);
    return ret;
}


发表于 2021-04-03 15:22:51 回复(0)
import java.util.*;

public class Solution {
    public ArrayList<Integer> first = new ArrayList<>();
    public ArrayList<Integer> middle = new ArrayList<>();
    public ArrayList<Integer> then = new ArrayList<>();
    public int[][] threeOrders (TreeNode root) {
        runOrder(root);
        int[][] result ={
            first.parallelStream().mapToInt(Integer::valueOf).toArray(),
            middle.parallelStream().mapToInt(Integer::valueOf).toArray(),
            then.parallelStream().mapToInt(Integer::valueOf).toArray()
        };
        return result;
    }
    
    public void runOrder(TreeNode root){
        if(root==null){
            return;
        }
        //前序
        first.add(root.val);
        runOrder(root.left);
         //中序
        middle.add(root.val);
        runOrder(root.right);
        //后续
        then.add(root.val);
    }
}

发表于 2021-03-12 17:19:37 回复(0)
前序,中序,后序遍历,没有花里胡哨的,非常直接的算法。
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>();
        
        preOrder(pre,root);//前序遍历
        inOrder(in,root); //中序遍历
        postOrder(post,root); //后序遍历
        
        int[][] array = new int[3][pre.size()];
        
        for(int i = 0; i < pre.size();i++){
            array[0][i] = pre.get(i);
            array[1][i] = in.get(i);
            array[2][i] = post.get(i);
        }
        
        return array;
    }
    
    public static void preOrder(ArrayList<Integer> pre,TreeNode root){
        if(root == null) return;
        pre.add(root.val);
        preOrder(pre,root.left);
        preOrder(pre,root.right);
    }
    
    public static void inOrder(ArrayList<Integer> in,TreeNode root){
        if(root == null) return;
        inOrder(in,root.left);
        in.add(root.val);
        inOrder(in,root.right);
    }
    
    public static void postOrder(ArrayList<Integer> post,TreeNode root){
        if(root == null) return;
        postOrder(post,root.left);
        postOrder(post,root.right);
        post.add(root.val);
    }
    
}



发表于 2021-03-10 11:34:57 回复(0)
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 flag0 = 0, flag1= 0, flag2 = 0;
    public int[][] threeOrders (TreeNode root) {
        //声明返回数组:这里用一个函数来获取树的size
        int[][] arr = new int[3][getTreeSize(root)];
        //递归遍历:(三种递归在一个函数里就可以了)
        travel(root, arr);
        return arr; //返回答案
    }
    public void travel(TreeNode root, int[][] arr){
        if(root==null){return;}
        arr[0][flag0++] = (root.val);
        travel(root.left, arr);
        arr[1][flag1++] = (root.val);
        travel(root.right, arr);
        arr[2][flag2++] = (root.val);
    }
    public int getTreeSize(TreeNode root){
        if(root==null){return 0;}
        return 1+getTreeSize(root.left)+getTreeSize(root.right);
    }
}
看注释就行
发表于 2021-03-08 15:49:36 回复(1)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    List<Integer> pre = new ArrayList<>();
	int i = 0;
	int[][] res;
	public int[][] threeOrders(TreeNode root) {
		preOrder(root);
		res = new int[3][pre.size()];
		for (Integer num : pre){
			res[0][i ++] = num;
		}
		i = 0;
		inOrder(root);
		i = 0;
		postOrder(root);
		return res;
	}

	private void postOrder(TreeNode root) {
		//使用栈的方式
		Stack<TreeNode> st = new Stack<>();
		TreeNode prev = null;
		while (root != null || !st.isEmpty()){
			while (root != null){
				st.push(root);
				root = root.left;
			}
			root = st.pop();
			// 此时应该遍历右子树了
			//如果右子树为空,或者右子树遍历完了,就该访问root节点了
			if(root.right == null || root.right == prev){
				res[2][i ++] = root.val;
				prev = root;
                //为了让栈能弹出下一个元素
				root = null;
			}else { //访问右孩子,并且需要把root重新入栈,因为此时root还没有被访问到
				st.push(root);
				root = root.right;
			}

		}
	}

	private void inOrder(TreeNode root) {
		//使用栈的方式
		Stack<TreeNode> st = new Stack<>();
		while (root != null || !st.isEmpty()){
			while (root != null){
				st.push(root);
				root = root.left;
			}
			root = st.pop();
			res[1][i ++] = root.val;
			root = root.right;
		}
	}

	void preOrder(TreeNode root) {
		//使用栈的方式遍历
		Stack<TreeNode> st = new Stack<>();
		st.push(root);
		while (!st.isEmpty()){
			TreeNode p = st.pop();
			pre.add(p.val);
			if(p.right != null){
				st.push(p.right);
			}
			if(p.left != null){
				st.push(p.left);
			}
		}
	}
}

发表于 2021-03-02 15:30:51 回复(0)