diff options
| author | crupest <crupest@outlook.com> | 2020-08-12 23:50:08 +0800 |
|---|---|---|
| committer | crupest <crupest@outlook.com> | 2020-08-12 23:50:08 +0800 |
| commit | 10b16d9c727d21eda445fc17f1717cf21a957e8a (patch) | |
| tree | 5f7795455344693ea72bc1cd114199d458120e80 /cpp/337.cpp | |
| parent | 3854234b797a8c015dc267bfe1e9e83cd1f08c3e (diff) | |
| download | solutions-10b16d9c727d21eda445fc17f1717cf21a957e8a.tar.gz solutions-10b16d9c727d21eda445fc17f1717cf21a957e8a.tar.bz2 solutions-10b16d9c727d21eda445fc17f1717cf21a957e8a.zip | |
Add problem 337 .
Diffstat (limited to 'cpp/337.cpp')
| -rw-r--r-- | cpp/337.cpp | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/cpp/337.cpp b/cpp/337.cpp new file mode 100644 index 0000000..655a4d0 --- /dev/null +++ b/cpp/337.cpp @@ -0,0 +1,38 @@ +#include <cstddef>
+
+struct TreeNode
+{
+ int val;
+ TreeNode *left;
+ TreeNode *right;
+ TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+struct SubTreeResult
+{
+ SubTreeResult(int use_root, int not_use_root) : use_root(use_root), not_use_root(not_use_root), max(use_root > not_use_root ? use_root : not_use_root) {}
+
+ const int use_root;
+ const int not_use_root;
+ const int max;
+};
+
+class Solution
+{
+public:
+ static SubTreeResult subtree_rob(TreeNode *root)
+ {
+ SubTreeResult left = root->left != NULL ? subtree_rob(root->left) : SubTreeResult{0, 0};
+ SubTreeResult right = root->right != NULL ? subtree_rob(root->right) : SubTreeResult{0, 0};
+ const auto use_root_value = root->val + left.not_use_root + right.not_use_root;
+ const auto not_use_root_value = left.max + right.max;
+ return SubTreeResult{use_root_value, not_use_root_value};
+ }
+
+ int rob(TreeNode *root)
+ {
+ if (root == NULL)
+ return 0;
+ return subtree_rob(root).max;
+ }
+};
|