最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

牛客网剑指Offer——树

互联网 admin 1浏览 0评论

牛客网剑指Offer——树

目录

  • 前言
  • 正文
    • 二叉树的深度
    • 按之字形顺序打印二叉树
    • 重建二叉树

前言

正文

二叉树的深度

题目

答案
code

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:int TreeDepth(TreeNode* root) {//注意深度,不就是一行加一行的结果吗queue<TreeNode*> q;if(root==nullptr)return 0;q.push(root);int result = 0;while(!q.empty()){int size = q.size();++result;while(size--){TreeNode* node = q.front();//该节点出队的时候,要将自己的子节点都入队if(node->left)q.push(node->left);if(node->right)q.push(node->right);q.pop();}}return result;}
};

按之字形顺序打印二叉树

题目

重建二叉树

题目

code

/*** 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>& pre, vector<int>& in) {//建树一般就采用递归建树的方式if(pre.size()==0||in.size()==0){return nullptr;}int rootVal = pre[0];int rootIndex;TreeNode* rootNode = new TreeNode(rootVal);for(int i = 0;i<in.size();i++){if(in[i]==rootVal)rootIndex = i;}vector<int> pre_left;vector<int> pre_right;vector<int> in_left;vector<int> in_right;for(int j = 0;j<rootIndex;j++){pre_left.push_back(pre[j+1]);in_left.push_back(in[j]);}for(int i = rootIndex+1;i<in.size();i++){pre_right.push_back(pre[i]);in_right.push_back(in[i]);}rootNode->left = buildTree(pre_left,in_left);rootNode->right = buildTree(pre_right,in_right);return rootNode;}
};

牛客网剑指Offer——树

目录

  • 前言
  • 正文
    • 二叉树的深度
    • 按之字形顺序打印二叉树
    • 重建二叉树

前言

正文

二叉树的深度

题目

答案
code

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:int TreeDepth(TreeNode* root) {//注意深度,不就是一行加一行的结果吗queue<TreeNode*> q;if(root==nullptr)return 0;q.push(root);int result = 0;while(!q.empty()){int size = q.size();++result;while(size--){TreeNode* node = q.front();//该节点出队的时候,要将自己的子节点都入队if(node->left)q.push(node->left);if(node->right)q.push(node->right);q.pop();}}return result;}
};

按之字形顺序打印二叉树

题目

重建二叉树

题目

code

/*** 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>& pre, vector<int>& in) {//建树一般就采用递归建树的方式if(pre.size()==0||in.size()==0){return nullptr;}int rootVal = pre[0];int rootIndex;TreeNode* rootNode = new TreeNode(rootVal);for(int i = 0;i<in.size();i++){if(in[i]==rootVal)rootIndex = i;}vector<int> pre_left;vector<int> pre_right;vector<int> in_left;vector<int> in_right;for(int j = 0;j<rootIndex;j++){pre_left.push_back(pre[j+1]);in_left.push_back(in[j]);}for(int i = rootIndex+1;i<in.size();i++){pre_right.push_back(pre[i]);in_right.push_back(in[i]);}rootNode->left = buildTree(pre_left,in_left);rootNode->right = buildTree(pre_right,in_right);return rootNode;}
};

与本文相关的文章

发布评论

评论列表 (0)

  1. 暂无评论