226. Invert Binary Tree/112. Path Sum

2019-11-08 03:26:15

字体：大中小

来源：转载

供稿：网友

Invert Binary Tree题目描述代码实现Path Sum题目描述代码实现

226. Invert Binary Tree

题目描述

Invert a binary tree.

4 / / 2 7 / / / /1 3 6 9

4 / / 7 2 / / / /9 6 3 1

Trivia: 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.

代码实现

/** * 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* invertTree(TreeNode* root) { if(!root) return root; TreeNode *l = root->left; root->left = root->right; root->right = l; if(root->left) invertTree(root->left); if(root->right) invertTree(root->right); return root; }};

更加简洁的写法：

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; }};

112. Path Sum

题目描述

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 1

return 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

上一篇：js时间函数扩展

下一篇：Spring基础教程网址