As part of the latest skills review \u2013 I am going back over my coding and trying to get better. Being honest I have been pleasantly surprised, but embarrassed, by some of the places I have found I have room for improvement. It is worth it though \u2013 cause sometimes you catch gems like this. <\/p>\n
When traversing trees, I tend to traverse them like they were graphs, and using queues. So for the problem of traverse a binary tree (not a BST), and return the largest value in each row I wrote the following code:<\/p>\n
\r\n\r\n vector largestValues(TreeNode* root) {\r\n vector maxrowval;\r\n \r\n if( root == NULL )\r\n return(maxrowval);\r\n \r\n queue > treesearch;\r\n treesearch.push(make_pair(root,0));\r\n \r\n while( !treesearch.empty()){\r\n TreeNode* curNode = treesearch.front().first;\r\n int curDepth = treesearch.front().second;\r\n treesearch.pop();\r\n \r\n if( maxrowval.size() <= curDepth ){\r\n maxrowval.push_back(curNode->val);\r\n }\r\n \r\n if( maxrowval[curDepth] < curNode->val ){\r\n maxrowval[curDepth] = curNode->val;\r\n }\r\n \r\n if( curNode->left != NULL ){\r\n treesearch.push(make_pair(curNode->left, curDepth+1));\r\n }\r\n \r\n if( curNode->right != NULL ){\r\n treesearch.push(make_pair(curNode->right, curDepth+1));\r\n }\r\n }\r\n \r\n return( maxrowval );\r\n }\r\n<\/code>\r\n<\/pre>\nWhat I just ran across was someone who wrote the following code for the same problem. He is using a list as opposed to a queue \u2013 but the logic of what we are doing is about the same. Only his double nested loop traversal of the list should be much faster. It avoids a lot of pushing and popping operations, and leaves the constructed search list intact. I am posting this here so I can come back and look at this later. This is the kind of thing I am going to want to stew on and see where else it might be a useful thing to have in the toolbox. <\/p>\n
\r\n\r\n vector largestValues(TreeNode* root) {\r\n vector result;\r\n list current;\r\n \r\n if (root != nullptr) {\r\n current.push_back(root);\r\n }\r\n \r\n while (current.size()) {\r\n int max_value = INT_MIN;\r\n int size = current.size();\r\n while (size) {\r\n TreeNode* node = current.front();\r\n max_value = max(max_value, node->val);\r\n current.pop_front();\r\n if (node->left != nullptr) {\r\n current.push_back(node->left);\r\n }\r\n \r\n if (node->right != nullptr) {\r\n current.push_back(node->right);\r\n }\r\n size--;\r\n }\r\n result.push_back(max_value);\r\n }\r\n \r\n return result;\r\n }\r\n<\/code>\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"As part of the latest skills review \u2013 I am going back over my coding and trying to get better. Being honest I have been pleasantly surprised, but embarrassed, by some of the places I have found I have room for improvement. It is worth it though \u2013 cause sometimes you catch gems like this. […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[39],"tags":[],"class_list":["post-1943","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1943","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1943"}],"version-history":[{"count":2,"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1943\/revisions"}],"predecessor-version":[{"id":1945,"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1943\/revisions\/1945"}],"wp:attachment":[{"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1943"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1943"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.hhhh.org\/joeboy\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1943"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}