列表

详情

NC45. 实现二叉树先序，中序和后序遍历

描述

给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

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

示例1

输入: 

{1,2,3}

输出: 

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

说明:

如题面图

示例2

输入: 

{}

输出: 

[[],[],[]]

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 2ms, 内存消耗: 300KB, 提交时间: 2021-09-17 

/**
 * 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> pre;
    vector<int> mid;
    vector<int> post;
    
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        if(root != nullptr) {
            preorder(root);
            midorder(root);
            postorder(root);
        }
        vector<vector<int>> res = {pre, mid, post};
        return res;
    }
    
    vector<int> preorder(TreeNode* root) {
        if(root == nullptr) return pre;
        stack<TreeNode*> tmp;
        tmp.push(root);
        while(!tmp.empty()) {
            auto x = tmp.top();
            tmp.pop();
            pre.push_back(x->val);
            if(x->right) tmp.push(x->right);
            if(x->left) tmp.push(x->left);
        }
        return pre;
    }
    
    vector<int> midorder(TreeNode* root) {
        stack<TreeNode *> s;
        while(s.size() || root) {
            while (root) {
                s.push(root);
                root = root->left;
            }
            if(s.size()) {
                root = s.top();
                s.pop();
                mid.push_back(root->val);
                root = root->right;
            }
        }
        return mid;
    }
    
    vector<int> postorder(TreeNode* root) {
        if(root == nullptr) return post;
        stack<TreeNode *> tmp;
        tmp.push(root);
        while(!tmp.empty()) {
            auto x = tmp.top();
            tmp.pop();
            post.push_back(x->val);
            if(x->left) tmp.push(x->left);
            if(x->right) tmp.push(x->right);
        }
        reverse(post.begin(), post.end());
        return post;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 304KB, 提交时间: 2021-09-19 

/**
 * 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 threeOrders(TreeNode* root, vector<vector<int> > &vect){
        if(!root)
            return;
        vect[0].push_back(root->val);
        threeOrders(root->left,vect);
        vect[1].push_back(root->val);
        threeOrders(root->right,vect);
        vect[2].push_back(root->val);
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int> > vect = {{},{},{}};
        threeOrders(root,vect);
        return vect;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 304KB, 提交时间: 2021-09-09 

/**
 * 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> pre;
    vector<int> mid;
    vector<int> post;
    
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        if(root != nullptr) {
            preorder(root);
            midorder(root);
            postorder(root);
        }
        vector<vector<int>> res = {pre, mid, post};
        return res;
    }
    vector<int> preorder(TreeNode* root) {
        if(root == NULL) {
            return pre;
        }
        stack<TreeNode*> tmp;
        tmp.push(root);
        while(!tmp.empty()) {
            auto x = tmp.top();
            tmp.pop();
            pre.push_back(x->val);
            if(x->right) {
                tmp.push(x->right);
            }
            if(x->left) {
                tmp.push(x->left);
            }
        }
        return pre;
    }
    
    vector<int> midorder(TreeNode* root) {
        stack<TreeNode *> s;
        while(s.size() || root) {//后面的循环中root为右子树中的根节点
            while(root) {
                s.push(root);
                root = root->left;
            }//对于当前访问的节点，先沿左边一直访问下去，直到叶子节点
            if(s.size()) {
                root = s.top();//然后才开始按进栈的顺序处理
                s.pop();
                mid.push_back(root->val);//处理完该节点
                root = root->right;//就去访问该节点的右子树
            }
        }
        return mid;
    }
    
    vector<int> postorder(TreeNode* root) {
        if(root == NULL) {
            return post;
        }
        stack<TreeNode *> tmp;
        tmp.push(root);
        while(!tmp.empty()) {
            auto x = tmp.top();
            tmp.pop();
            post.push_back(x->val);
            if(x->left) {
                tmp.push(x->left);
            }
            if(x->right) {
                tmp.push(x->right);
            }
        }
        reverse(post.begin(), post.end());
        return post;
    }
    
    
};

C++ 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2021-09-12 

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

    vector<int> res;
    // st.push(root);
    while(p!=nullptr||!st.empty()){
        if(p!=nullptr){
            // if(p->right!=nullptr)
            //     st.push(p->right);
            // if(p->left !=nullptr)
                st.push(p);
            p=p->left;
        }else{
            p=st.top();
            if((p->left==last_print&&p->right==nullptr) || p->right == last_print || (p->left==nullptr&&p->right==nullptr)){
                st.pop();
                res.push_back(p->val);
                last_print = p;
                p=nullptr;
            }else{
                // st.push(p->right);
                p=p->right;
            }
        }
    }
    return res;
}  
    vector<vector<int> > threeOrders(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur=root;
        vector<vector<int>> res;
        vector<int> pre_res = preOrder(root);
        vector<int> mid_res = midOrder(root);
        vector<int> post_res = postOrder(root);
        res.push_back(pre_res);
        res.push_back(mid_res);
        res.push_back(post_res);
        return res;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 316KB, 提交时间: 2021-09-12 

#include<stdio.h>
/**
 * 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> pre;
    vector<int> mid;
    vector<int> post;
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        if(root != nullptr){//nullptr任意指针类型
            preorder(root);
            midorder(root);
            postorder(root);
        }
        vector<vector<int>>res = {pre,mid,post};
        return res;
    }
    vector<int> preorder(TreeNode* root) {//中左右
        if(root==NULL){
            return pre;
        }
        stack<TreeNode*> tmp;//设置栈对象
        tmp.push(root);//保存根结点
        while(!tmp.empty()){
            auto x = tmp.top();
            tmp.pop();//出栈
            pre.push_back(x->val);//存入容器
            if(x->right){
                tmp.push(x->right);
            }
            if(x->left){
                tmp.push(x->left);
            }
        }
        return pre;
    }
    vector<int> midorder(TreeNode* root) {//左中右
        stack<TreeNode *> s;//设置栈对象
        while (s.size() || root){
            while (root){
                s.push(root);
                root = root->left;//先左
            }
            if (s.size()){
                root = s.top();
                s.pop();
                mid.push_back(root->val);
                root = root->right;
            }
        }
        return mid;
}
    vector<int> postorder(TreeNode* root) {//左右中
        if(root==NULL){
            return post;
        }
        stack<TreeNode*> tmp;//设置栈对象
        tmp.push(root);
        while(!tmp.empty()){
            auto x = tmp.top();
            tmp.pop();
            post.push_back(x->val);
            if(x->left){
                tmp.push(x->left);
            }
            if(x->right){
                tmp.push(x->right);
            }
        }
        reverse(post.begin(),post.end());
        return post;
    }
};

上一题

© 2024 nowcoder.com