Python教程

LeetCode题解(1740):找到二叉树中的距离(Python)

本文主要是介绍LeetCode题解(1740):找到二叉树中的距离(Python),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:原题链接(中等)

标签:树、二叉树、深度优先搜索、广度优先搜索

解法时间复杂度空间复杂度执行用时
Ans 1 (Python) O ( N ) O(N) O(N) O ( N ) O(N) O(N)108ms (47.50%)
Ans 2 (Python)
Ans 3 (Python)

解法一:

class Solution:
    def findDistance(self, root: TreeNode, p: int, q: int) -> int:
        ans = 0

        def dfs(node):
            nonlocal ans
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            if left > 0 and right > 0:
                ans = left + right
                return 0
            elif left > 0 or right > 0:
                if node.val == p or node.val == q:
                    ans = max(left, right)
                    return 0
                else:
                    return max(left, right) + 1
            elif node.val == p and node.val == q:
                ans = 0
                return 0
            elif node.val == p or node.val == q:
                return 1
            else:
                return 0

        dfs(root)
        return ans
这篇关于LeetCode题解(1740):找到二叉树中的距离(Python)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!