408算法题leetcode--第16天

144. 二叉树的前序遍历

• 144. 二叉树的前序遍历
• 思路：递归和非递归
• 时间：O(n)；空间：O(n)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int>ret;void pre(TreeNode* root){if(root != nullptr){ret.push_back(root->val);pre(root->left);pre(root->right);}}vector<int> preorderTraversal(TreeNode* root) {pre(root);return ret;}
};

102. 二叉树的层序遍历

• 102. 二叉树的层序遍历
• 思路：bfs，队列
• 时间：O(n)；空间：O(n)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>>ret;if(!root) return ret;queue<TreeNode*>q;q.push(root);while(!q.empty()){vector<int>level;int size = q.size();for(int i = 0; i < size; i++){TreeNode* temp = q.front();q.pop();level.push_back(temp->val);if(temp->left) q.push(temp->left);if(temp->right) q.push(temp->right);}ret.push_back(level);}return ret;}
};

199. 二叉树的右视图

• 199. 二叉树的右视图
• 思路和时间，空间：同上

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int>ret;if(!root) return ret;queue<TreeNode*>q;q.push(root);while(!q.empty()){int size = q.size();for(int i = 0; i < size; i++){TreeNode* temp = q.front();q.pop();if(i == size - 1){ret.push_back(temp->val);}if(temp->left) q.push(temp->left);if(temp->right) q.push(temp->right);}}return ret;}
};

404. 左叶子之和

• 404. 左叶子之和
• 思路：dfs
• 时间和空间：O(n)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int traverse(TreeNode* root, bool is_left){if(!root) return 0;  // 节点为空if(!root->left && !root->right && is_left) return root->val;  // 叶子节点且为左子树 return traverse(root->left, true) + traverse(root->right, false);}int sumOfLeftLeaves(TreeNode* root) {// 三种情况：1. 节点为空；2. 叶子节点且为左子树 ; 3. elsereturn traverse(root, false);}
};

104. 二叉树的最大深度

• 104. 二叉树的最大深度
• 思路和时间空间：同上

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {// 1. 有左右儿子，2. 空, 3. elseif(!root) return 0;int max_v = 1;if(root->left) max_v = maxDepth(root->left) + 1;if(root->right) max_v = max(max_v, maxDepth(root->right) + 1);return max_v;}
};