{"id":493,"date":"2022-06-22T05:58:12","date_gmt":"2022-06-21T21:58:12","guid":{"rendered":"https:\/\/www.wennroy.com\/?p=493"},"modified":"2022-06-22T06:00:41","modified_gmt":"2022-06-21T22:00:41","slug":"dfs-bfs-binary-tree","status":"publish","type":"post","link":"https:\/\/wennroy.com\/index.php\/2022\/06\/22\/dfs-bfs-binary-tree\/","title":{"rendered":"DFS\/BFS \u4e8c\u53c9\u6811"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">\u4ece <a href=\"https:\/\/leetcode.cn\/problems\/find-bottom-left-tree-value\" data-type=\"URL\" data-id=\"https:\/\/leetcode.cn\/problems\/find-bottom-left-tree-value\">\u5bfb\u627e\u6700\u5e95\u5c42\u6700\u5de6\u8fb9\u7684\u7ed3\u70b9<\/a><a href=\"https:\/\/leetcode.cn\/problems\/find-bottom-left-tree-value\" data-type=\"URL\"> <\/a> \u590d\u4e60DFS \u548c BFS \u5728\u4e8c\u53c9\u6811\u4e2d\u7684\u8fd0\u7528\u3002\u4ee5\u4e0b\u662f\u81ea\u5df1\u778e\u5199\u7684\u7248\u672c\u3002<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution:\n    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n\n        def dfs(self, root: TreeNode) -> list[int]:\n            if not root.left and not root.right:\n                return [root.val, 0]  # [val, level]\n            elif not root.left:\n                ans = dfs(self, root.right)\n                return [ans[0], ans[1] + 1]\n\n            elif not root.right:\n                ans = dfs(self, root.left)\n                return [ans[0], ans[1] + 1]\n            else:\n                ans_left, ans_right = dfs(self, root.left), dfs(self, root.right)\n                if ans_left[1] >= ans_right[1]:\n                    ans = ans_left\n                else:\n                    ans = ans_right\n\n                return [ans[0], ans[1] + 1]\n\n        return dfs(self, root)[0]<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u81ea\u5df1\u5199\u7684DFS\u867d\u7136\u5f88\u5bb9\u6613\u7406\u89e3\uff0c\u4f46\u6709\u591a\u6b21\u91cd\u590d\u7684\u5206\u7c7b\u3002\u5b8c\u5168\u53ef\u4ee5\u5728\u9996\u884c\u5bf9node\u8fdb\u884c\u5224\u5b9a\u662f\u5426\u4e3aNone\uff0c\u4ee5\u7f29\u51cf\u6574\u4f53DFS\u7684\u7bc7\u5e45\u3002\u4e00\u5f00\u59cb\u8fd9\u4e48\u5199\u4e5f\u662f\u7406\u89e3\u9519\u4e86\u9898\u610f\uff0c\u4ee5\u4e3a\u662f\u8981\u5199\u6700\u5e95\u5c42\u7684\u5de6\u7ed3\u70b9\uff0c\u6240\u4ee5\u505a\u51fa\u4e86\u4e00\u70b9\u53d8\u5316\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ee5\u4e0b\u7ed9\u51fa\u6807\u7b54\u7684DFS\u548cBFS<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># DFS\nclass Solution:\n    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n        curVal = curHeight = 0\n        def dfs(node: Optional[TreeNode], height: int) -> None:\n            if node is None:\n                return\n            height += 1\n            dfs(node.left, height)\n            dfs(node.right, height)\n            nonlocal curVal, curHeight\n            if height > curHeight:\n                curHeight = height\n                curVal = node.val\n        dfs(root, 0)\n        return curVal\n# BFS\nclass Solution:\n    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n        q = deque([root])\n        while q:\n            node = q.popleft()\n            if node.right:\n                q.append(node.right)\n            if node.left:\n                q.append(node.left)\n            ans = node.val\n        return ans\n\n'''\n\u4f5c\u8005\uff1aLeetCode-Solution\n\u94fe\u63a5\uff1ahttps:\/\/leetcode.cn\/problems\/find-bottom-left-tree-value\/solution\/zhao-shu-zuo-xia-jiao-de-zhi-by-leetcode-weeh\/\n\u6765\u6e90\uff1a\u529b\u6263\uff08LeetCode\uff09\n\u8457\u4f5c\u6743\u5f52\u4f5c\u8005\u6240\u6709\u3002\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u8054\u7cfb\u4f5c\u8005\u83b7\u5f97\u6388\u6743\uff0c\u975e\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u6ce8\u660e\u51fa\u5904\u3002\n'''<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">DFS\u5f88\u6e05\u6670\u660e\u4e86\uff0c\u4e3b\u8981\u5b66\u4e60BFS\u7684\u5199\u6cd5\u3002\u8fd9\u91cc\u5f15\u7528\u4e86 <strong>deque<\/strong> \u6a21\u5757\uff0c\u96b6\u5c5e\u4e8e <strong>collections<\/strong> \u3002\u672c\u8d28\u4e0a\u7c7b\u4f3c\u4e8e\u5217\u8868\uff0c\u4f46\u4e24\u8fb9\u90fd\u53ef\u4ee5\u8fdb\u51fa\uff0c\u6709\u5feb\u6377\u6dfb\u52a0\u548c\u5220\u9664\u7684\u65b9\u6cd5\u3002<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">from collections import deque\n\nd = deque([5])\n\n# append\nd.append(10)\nd.append(15)\n\n# pop\nd.pop()\nd.leftpop()\n\n# maxlen\nd=deque(maxlen=20)\nfor i in range(30):\n    d.append(str(i))\n#  \u6b64\u65f6d\u7684\u503c\u4e3ad=deque(['10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26', '27', '28', '29'], maxlen=20)\n#  \u53ef\u89c1\u5f53\u9650\u5236\u957f\u5ea6\u7684deque\u589e\u52a0\u8d85\u8fc7\u9650\u5236\u6570\u7684\u9879\u65f6\uff0c\u53e6\u4e00\u8fb9\u7684\u9879\u4f1a\u81ea\u52a8\u5220\u9664\u3002\n\n# extend\nd=deque([1,2,3,4,5])\nd.extend([0])\n# \u90a3\u4e48\u6b64\u65f6d=deque([1,2,3,4,5,0])\nd.extendleft([6,7,8])\n# \u6b64\u65f6d=deque([8, 7, 6, 1, 2, 3, 4, 5, 0])\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4ece \u5bfb\u627e\u6700\u5e95\u5c42\u6700\u5de6\u8fb9\u7684\u7ed3\u70b9 \u590d\u4e60DFS \u548c BFS &hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[49,6,48,18],"tags":[],"class_list":["post-493","post","type-post","status-publish","format-standard","hentry","category-dfs-bfs","category-leetcode","category-48","category-ergodic"],"_links":{"self":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/493","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/comments?post=493"}],"version-history":[{"count":1,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/493\/revisions"}],"predecessor-version":[{"id":494,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/493\/revisions\/494"}],"wp:attachment":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/media?parent=493"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/categories?post=493"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/tags?post=493"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}