N叉树问题-LeetCode 429、589、590、105、106(构建二叉树,N叉树遍历)

作者:TeddyZhang,公众号:算法工程师之路

1

编程题

二叉树拓展到N叉树思路

  • 先序中入栈顺序先右后左 --> 孩子节点数组从右向左入栈
  • 后序中入栈顺序先左后右 --> 孩子节点数组从左向右入栈

【LeetCode #429】N叉树的层序遍历

给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。 例如,给定一个 3叉树 :

返回其层序遍历:

[ [1], [3,2,4], [5,6] ]

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        queue<Node*> que;
        if(root == nullptr) return res;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            while(size--){
                Node* tmp = que.front();
                que.pop();
                vec.push_back(tmp->val);
                for(auto child: tmp->children){
                    if(child != nullptr){
                        que.push(child);
                    }
                }
            }
            res.push_back(vec);
        }
        return res;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

【LeetCode #589】N叉树的前序遍历

给定一个 N 叉树,返回其节点值的前序遍历。 例如,给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        if(root == nullptr)  return res;
        stack<Node*> sta;
        sta.push(root);
        while(!sta.empty()){
            Node* tmp = sta.top();
            sta.pop();
            res.push_back(tmp->val);
            auto it = tmp->children.rbegin();
            for(; it != tmp->children.rend(); it++){
                if(*it != nullptr){
                    sta.push(*it);
                }
            }
        }
        return res;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

【LeetCode #590】N叉树的后序遍历

给定一个 N 叉树,返回其节点值的后序遍历。 例如,给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if(root == nullptr) return res;
        stack<Node*> sta;
        sta.push(root);
        while(!sta.empty()){
            Node* tmp = sta.top();
            sta.pop();
            res.insert(res.begin(), tmp->val);
            for(auto node: tmp->children){
                if(node != nullptr){
                    sta.push(node);
                }
            }
        }
        return res;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

【LeetCode #105】从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。

例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

解题思路:

使用分治的思想,从一个节点开始递归的构建其左右子树,将一个问题分成多个子问题,这种递归的思路非常简单,下面代码边界也十分清晰!

由于preorder中的第一个元素必定为根节点,那么可以在inorder中去查找该节点(题中说元素不值重复),找到之后得到索引 i, 根据中序遍历的性质,索引 i 的左边的数值为根节点的左子树的中序遍历,而对应到preorder中索引1到i+1为根节点的左子树的前序遍历!同理得到右子树的前序和中序遍历,那么这样就变成了两个个子问题 --> 递归的构建根节点的左右子树,即得到答案!

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == )  return nullptr;
        int i = ;
        while(inorder[i] != preorder[]){   // 找到中序遍历树根的位置
            i++;
        }
        TreeNode* root = new TreeNode(preorder[]);
        // 注意去除第一个preorder[0]
        vector<int> preleft(preorder.begin()+, preorder.begin()+i+);   //左子树的preorder
        vector<int> preright(preorder.begin()+i+, preorder.end());      //右子树的preorder
        vector<int> inleft(inorder.begin(), inorder.begin()+i);          //左子树的inorder
        vector<int> inright(inorder.begin()+i+, inorder.end());         //右子树的inorder
        root->left = buildTree(preleft, inleft);
        root->right = buildTree(preright, inright);
        return root;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

【LeetCode #106】从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。

例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:

解题思路:

使用分治的思想,从一个节点开始递归的构建其左右子树,将一个问题分成多个子问题,这种递归的思路非常简单,下面代码边界也十分清晰!

由于postorder中的最后一个元素必定为根节点,那么可以在inorder中去查找该节点(题中说元素不值重复),找到之后得到索引 i, 根据中序遍历的性质,索引 i 的左边的数值为根节点的左子树的中序遍历,而对应到postorder中索引 0 到 i 为根节点的左子树的前序遍历!同理得到右子树的后序和中序遍历,那么这样就变成了两个个子问题 --> 递归的构建根节点的左右子树,即得到答案!

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == )  return nullptr;
        int n = postorder.size() - , i = ;
        while(inorder[i] != postorder[n]){
            i++;
        }
        TreeNode* root = new TreeNode(postorder[n]);
        vector<int> inleft(inorder.begin(), inorder.begin()+i);         //左子树的inorder
        vector<int> inright(inorder.begin()+i+, inorder.end());        //右子树的inorder
        vector<int> postleft(postorder.begin(), postorder.begin()+i);   //左子树的postorder
        vector<int> postright(postorder.begin()+i, postorder.end()-1);  //右子树的postorder
        root->left = buildTree(inleft, postleft);
        root->right = buildTree(inright, postright);
        return root;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小詹同学

统治世界的 10 大算法,你知道几个?

一篇有趣的文章《统治世界的十大算法》中,作者George Dvorsky试图解释算法之于当今世界的重要性,以及哪些算法对人类文明最为重要。

8620
来自专栏小詹同学

小白也能看懂的Pandas实操演示教程(上)

pandas中有两类非常重要的数据结构,就是序列Series和数据框DataFrame.Series类似于NumPy中的一维数组,可以使用一维数组的可用函数和方...

7240
来自专栏IT大咖说

程序员自己能写测试的话,还要测试人员做什么?测试表示很无辜

本篇想要通过探讨这些问题背后的困难,来说明程序员怎样通过编写自测代码更有效率的进行开发。

10220
来自专栏机器学习与统计学

围观~山东省的小学生Python编程入门都学的什么?

上午刷微博,又看到关于编程从娃娃抓起的梗,就想起之前看到的新闻,教育部从今年开始将在中小学推广编程教育。

15710
来自专栏机器学习与统计学

干货 | 27 个问题,告诉你 Python 为什么如此设计?

https://docs.python.org/zh-cn/3.7/faq/design.html

5810
来自专栏DotNet程序园

造轮子了!NETCore跨平台UI框架,CPF

CPF(暂时命名)(Cross platform framework),模仿WPF的框架,支持NETCore的跨平台UI框架,暂时不够完善,只用于测试,暂时只支...

6510
来自专栏程序员的成长之路

是否注意过isEmpty 和 isBlank 区别?

org.apache.commons.lang.StringUtils 类提供了 String 的常用操作,最为常用的判空有如下两种 isEmpty(Strin...

6330
来自专栏DotNet程序园

​.NET手撸2048小游戏

2048是一款益智小游戏,得益于其规则简单,又和 2的倍数有关,因此广为人知,特别是广受程序员的喜爱。

13130
来自专栏DotNet程序园

微软并发Key-Value存储库FASTER介绍

微软支持并发的Key-Value 存储库有C++与C#两个版本。号称迄今为止最快的并发键值存储。下面是C#版本翻译:

6120
来自专栏DotNet程序园

.NET如何写正确的“抽奖”——数组乱序算法

数组乱序算法常用于抽奖等生成临时数据操作。就拿年会抽奖来说,如果你的算法有任何瑕疵,造成了任何不公平,在年会现场 code review时,搞不好不能活着走出去...

10330

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励