经典算法专区：找树左下角的值（二）
接上文小编来分享一下解题思路深度优先搜索使用 height 记录遍历到的节点的高度curVal 记录高度在 curHeight 的最左节点的值。在深度优先搜索时我们先搜索当前节点的左子节点再搜索当前节点的右子节点然后判断当前节点的高度 height 是否大于 curHeight 如果是那么将 curVal 设置为当前结点的值curHeight 设置为 height 。因为我们先遍历左子树然后再遍历右子树所以对同一高度的所有节点最左节点肯定是最先被遍历到的。代码Python3class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) - int: curVal curHeight 0 def dfs(node: Optional[TreeNode], height: int) - None: if node is None: return height 1 dfs(node.left, height) dfs(node.right, height) nonlocal curVal, curHeight if height curHeight: curHeight height curVal node.val dfs(root, 0) return curValCclass Solution { public: void dfs(TreeNode *root, int height, int curVal, int curHeight) { if (root nullptr) { return; } height; dfs(root-left, height, curVal, curHeight); dfs(root-right, height, curVal, curHeight); if (height curHeight) { curHeight height; curVal root-val; } } int findBottomLeftValue(TreeNode* root) { int curVal, curHeight 0; dfs(root, 0, curVal, curHeight); return curVal; } };Javaclass Solution { int curVal 0; int curHeight 0; public int findBottomLeftValue(TreeNode root) { int curHeight 0; dfs(root, 0); return curVal; } public void dfs(TreeNode root, int height) { if (root null) { return; } height; dfs(root.left, height); dfs(root.right, height); if (height curHeight) { curHeight height; curVal root.val; } } }复杂度分析时间复杂度O(n) 其中 n 是二叉树的节点树目。需要遍历 n 个节点。空间复杂度O(n) 递归栈需要占用 O(n) 的空间。
