Recursive Depth First Search Algorithm to Compute the Sum of Nod
- 时间:2020-09-12 10:06:27
- 分类:网络文摘
- 阅读:99 次
Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)
If there are no nodes with an even-valued grandparent, return 0.
binary-tree-grandparent
Example 1:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.Constraints:
The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.Hints:
Traverse the tree keeping the parent and the grandparent.
If the grandparent of the current node is even-valued, add the value of this node to the answer.
Depth First Search Algorithm to Pass the Parent and GrandParent Nodes
When we do a DFS (Depth First Search) Algorithm from the root, we can pass down the parent, and the grandparent nodes. Thus, when conditions are met (the grandparent nodes have even values), we accumulate the sum.
The implementation is done via Recursion, and the runtime complexity is O(N) where N is the number of the nodes in the binary tree. The space requirement is also O(N) where the binary tree in worst case may become the singly linked list and the usage of recursion yields the stack-calls.
The C++ code to traverse the binary tree in DFS:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | /** * 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 sumEvenGrandparent(TreeNode* root) { dfs(root, nullptr, nullptr); return sum; } private: int sum = 0; void dfs(TreeNode* root, TreeNode* parent, TreeNode* grandparent) { if (root == nullptr) return; if (grandparent != nullptr && grandparent->val % 2 == 0) { sum += root->val; } dfs(root->left, root, parent); dfs(root->right, root, parent); } }; |
/** * 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 sumEvenGrandparent(TreeNode* root) { dfs(root, nullptr, nullptr); return sum; } private: int sum = 0; void dfs(TreeNode* root, TreeNode* parent, TreeNode* grandparent) { if (root == nullptr) return; if (grandparent != nullptr && grandparent->val % 2 == 0) { sum += root->val; } dfs(root->left, root, parent); dfs(root->right, root, parent); } };
And here is the Java code to visit the binary tree in DFS:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private int sum = 0; public int sumEvenGrandparent(TreeNode root) { dfs(root, null, null); return sum; } private void dfs(TreeNode root, TreeNode parent, TreeNode grandparent) { if (root == null) return; if (grandparent != null && (grandparent.val % 2 == 0)) { sum += root.val; } dfs(root.left, root, parent); dfs(root.right, root, parent); } } |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private int sum = 0; public int sumEvenGrandparent(TreeNode root) { dfs(root, null, null); return sum; } private void dfs(TreeNode root, TreeNode parent, TreeNode grandparent) { if (root == null) return; if (grandparent != null && (grandparent.val % 2 == 0)) { sum += root.val; } dfs(root.left, root, parent); dfs(root.right, root, parent); } }
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:如何设置WordPress的RSS feed更新频率 利用WordPress开发者调试模式解决PHP500内部服务器错误 正确屏蔽 WordPress 版本号的代码 WordPress插件WP First Letter Avatar代码版 让WordPress文章内链接在新窗口打开的方法 如何让wrodpress在分类列表页显示其下子分类文章列表 如何下载WordPress官网插件的旧版本 剧场有多少座位 荷叶覆盖面积正好占池塘面积的四分之一 世界杯一共要进行多少场比赛
- 评论列表
-
- 添加评论