Given a binary tree, find the leftmost value in the last row of the tree.
Example: Input:
1 / / 2 3 / / /4 5 6 / 7Output: 7 Note: You may assume the tree (i.e., the given root node) is not NULL.
思路：DFS，記錄當前最深深度第一個訪問節點的值，即為答案
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * 思路：DFS，記錄當前最深深度第一個訪問節點的值，即為答案 */class Solution {PRivate: void dfs(TreeNode *root, int cur_dep, int *mx_dep, int *ret) { if (*mx_dep < cur_dep) { *mx_dep = cur_dep; *ret = root->val; } if (root->left) dfs(root->left, cur_dep + 1, mx_dep, ret); if (root->right) dfs(root->right, cur_dep + 1, mx_dep, ret); }public: int findBottomLeftValue(TreeNode* root) { if (!root) return -1; int ret = root->val, dep = 0; dfs(root, 0, &dep, &ret); return ret; }};Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
Examples 1 Input:
5 / /2 -3return [2, -3, 4], since all the values happen only once, return all of them in any order. Examples 2 Input:
5 / /2 -5return [2], since 2 happens twice, however -5 only occur once. Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.
思路：DFS+哈希，用哈希表記錄DFS返回的結果，然后遍歷哈希表求答案
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * 思路：DFS+哈希，用哈希表記錄DFS返回的結果，然后遍歷哈希表求答案 */class Solution {private: int dfs(TreeNode *root, unordered_map<int, int> &mp, int *max_cnt) { if (!root) return 0; int ret = root->val; ret += dfs(root->left, mp, max_cnt); ret += dfs(root->right, mp, max_cnt); mp[ret]++; if (*max_cnt < mp[ret]) *max_cnt = mp[ret]; return ret; }public: vector<int> findFrequentTreeSum(TreeNode* root) { unordered_map<int, int> mp; int max_cnt = 0; dfs(root, mp, &max_cnt); vector<int> ret; for (auto e: mp) { if (e.second == max_cnt) ret.push_back(e.first); } return ret; }};Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree
1 / / 2 3 / /4 5as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
思路：遞歸DFS
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * 思路：遞歸DFS */class Codec {private: void serialize_helper(string &ret, TreeNode *root) { if (!root) { ret += "# "; return; } else ret += to_string(root->val) + " "; serialize_helper(ret, root->left); serialize_helper(ret, root->right); } void deserialize_helper(stringstream &ss, TreeNode **p) { while (!ss.eof() && ss.peek() == ' ') ss.get(); if (ss.eof()) return; if (ss.peek() == '#') { // nullptr ss.get(); return; } int val; ss >> val; *p = new TreeNode(val); deserialize_helper(ss, &((*p)->left)); deserialize_helper(ss, &((*p)->right)); }public: // Encodes a tree to a single string. string serialize(TreeNode* root) { string ret; serialize_helper(ret, root); return ret; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { TreeNode *ret = nullptr; TreeNode **p = &ret; stringstream ss(data); deserialize_helper(ss, p); return ret; }};// Your Codec object will be instantiated and called as such:// Codec codec;// codec.deserialize(codec.serialize(root));Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
思路：非遞歸版本，優先遍歷左子樹，用棧記錄當前節點以及當前節點的深度
/** * 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: int maxDepth(TreeNode* root) { stack<pair<TreeNode *, int> > stk; int dep = 1; for (; root; root = root->left) stk.emplace(root, dep++); int ret = 0; while (!stk.empty()) { TreeNode *cur; tie(cur, dep) = stk.top(); stk.pop(); ret = max(ret, dep); for (cur = cur->right, dep++; cur; cur = cur->left, dep++) stk.emplace(cur, dep); } return ret; }};/** * 遞歸版 */class Solution {public: int maxDepth(TreeNode* root) { if (!root) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; }};新聞熱點
疑難解答
