题解 | #实现二叉树先序,中序和后序遍历#

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

http://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362

二叉树的先序、中序和后序遍历的要点是:左右顺序固定,先序是根节点最先访问,后序是根节点最后访问,即三种访问顺序是根据根节点的访问顺序来命名的。在访问时递归即可。
先序:根左右
中序:左根右
后序:左右根

/**
 * 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> > rst;

        rst.push_back(pre_order(root));
        rst.push_back(mid_order(root));
        rst.push_back(post_order(root));

        return rst;
    }

    //根左右
    vector<int> pre_order(TreeNode* root)
    {

        vector<int> rst;
        if(!root)
            return rst;

        //将根结点的val加入到rst中;
        rst.push_back(root->val);

        //如果有左孩子则统计左孩子;
        if(root->left)
            for(auto& o:pre_order(root->left))
                rst.push_back(o);

        //如果有右孩子则统计右孩子;
        if(root->right)
            for(auto& o:pre_order(root->right))
                rst.push_back(o);

        return rst;
    }

    //左根右
    vector<int> mid_order(TreeNode* root)
    {

        vector<int> rst;
        if(!root)
            return rst;

        //如果有左孩子则统计左孩子;
        if(root->left)
            for(auto& o:mid_order(root->left))
                rst.push_back(o);

        //将根结点的val加入到rst中;
        rst.push_back(root->val);

        //如果有右孩子则统计右孩子;
        if(root->right)
            for(auto& o:mid_order(root->right))
                rst.push_back(o);

        return rst;
    }

    //左右根
    vector<int> post_order(TreeNode* root)
    {

        vector<int> rst;
        if(!root)
            return rst;

        //如果有左孩子则统计左孩子;
        if(root->left)
            for(auto& o:post_order(root->left))
                rst.push_back(o);

        //如果有右孩子则统计右孩子;
        if(root->right)
            for(auto& o:post_order(root->right))
                rst.push_back(o);

        //将根结点的val加入到rst中;
        rst.push_back(root->val);

        return rst;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务