Invert Binary Tree題目描述代碼實現Path Sum題目描述代碼實現
Invert a binary tree.
4 / / 2 7 / / / /1 3 6 9to
4 / / 7 2 / / / /9 6 3 1Trivia: This PRoblem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
更加簡潔的寫法：
class Solution {public: TreeNode* invertTree(TreeNode* root) { if (root) { invertTree(root->left); invertTree(root->right); std::swap(root->left, root->right); } return root; }};使用廣度優先的算法：
class Solution {public: TreeNode* invertTree(TreeNode* root) { std::stack<TreeNode*> stk; stk.push(root); while (!stk.empty()) { TreeNode* p = stk.top(); stk.pop(); if (p) { stk.push(p->left); stk.push(p->right); std::swap(p->left, p->right); } } return root; }};Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example: Given the below binary tree and sum = 22,
5 / / 4 8 / / / 11 13 4 / / / 7 2 1return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
這種方法是使用了DFS。
class Solution {public: bool isEqual(TreeNode* root, int sum, int leafsum) { if(root == NULL) return false; leafsum += root->val; if(sum == leafsum && !root->left && !root->right) return true; return isEqual(root->left, sum, leafsum) || isEqual(root->right, sum, leafsum); } bool haspathSum(TreeNode* root, int sum) { if(!root) return false; int leafsum = 0; return isEqual(root, sum, leafsum); }};當然使用BFS也是可以的。 在leetcode的discussion部分，里面有的是BFS的做法。這里有兩個實現： 其中一個做法不需要額外的數據結構在記錄整個過程中的sum：
class Solution {public: bool hasPathSum(TreeNode* root, int sum) { stack<TreeNode*> st; TreeNode* itr = root; while(itr != NULL || !st.empty()){ while(itr != NULL){ if(itr->right != NULL) st.push(itr->right); st.push(itr); sum -= itr->val; itr = itr->left; } TreeNode* temp = st.top(); st.pop(); if(temp->left == NULL && temp->right == NULL && sum == 0) return true; if(temp->right && !st.empty() && temp->right == st.top()){ itr = st.top(); st.pop(); st.push(temp); }else{ sum += temp->val; } } return false; }};另外一種BFS更容易理解，使用的是普通的廣度優先策略，用pair記錄節點以及當前的和。
bool hasPathSum1(TreeNode* root, int sum) { if(root==nullptr) return false; vector<pair<TreeNode*, int>> stack; auto cur=make_pair(root, root->val); while(cur.first || stack.size()){ while(cur.first){ stack.push_back(cur); if(cur.first->left==nullptr) cur=make_pair(cur.first->left, 0); else cur=make_pair(cur.first->left, cur.second+cur.first->left->val); } auto node=stack.back(); stack.pop_back(); if(node.first->left==nullptr && node.first->right==nullptr) if(node.second==sum) return true; if(node.first->right) cur=make_pair(node.first->right, node.second+node.first->right->val); } return false;}在這里我覺得廣度優先和深度優先各有優勢，廣度優先適合比較短的路徑，而深度優先適合更加長的，窄的路徑。
參考鏈接：
https://discuss.leetcode.com/topic/41568/comparison-of-c-non-recursive-solutions
新聞熱點
疑難解答
