牛客网剑指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;}
};