首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

查找二叉树的最深节点。如果多个节点位于最深层,则返回最右侧的Node。(答案在描述中)

查找二叉树的最深节点可以通过深度优先搜索(DFS)或广度优先搜索(BFS)来实现。以下是使用DFS的方法:

  1. 定义一个变量maxDepth来记录当前最大深度,初始值为0。
  2. 定义一个变量rightMostNode来记录最右侧的节点,初始值为null。
  3. 从根节点开始进行DFS遍历,传入当前节点、当前深度和maxDepth。
  4. 在DFS函数中,首先判断当前节点是否为空,如果为空则返回。
  5. 如果当前深度大于maxDepth,则更新maxDepth为当前深度,并将rightMostNode指向当前节点。
  6. 递归遍历当前节点的左子树,深度加1。
  7. 递归遍历当前节点的右子树,深度加1。
  8. 返回rightMostNode作为结果。

以下是示例代码:

代码语言:txt
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findDeepestNode(root):
    maxDepth = 0
    rightMostNode = None

    def dfs(node, depth, maxDepth, rightMostNode):
        if not node:
            return

        if depth > maxDepth:
            maxDepth = depth
            rightMostNode = node

        dfs(node.left, depth + 1, maxDepth, rightMostNode)
        dfs(node.right, depth + 1, maxDepth, rightMostNode)

    dfs(root, 1, maxDepth, rightMostNode)
    return rightMostNode

这个算法的时间复杂度是O(n),其中n是二叉树中的节点数。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

没有搜到相关的合辑

领券