美文网首页
每日算法题—包含所有最深结点的最小子树

每日算法题—包含所有最深结点的最小子树

作者: 程田 | 来源:发表于2019-10-04 21:12 被阅读0次

题目描述

给定一棵二叉树,求包含所有最深节点的最小子树
最深节点:深度最大的节点,深度即当前节点到根节点的最短距离
包含所有最深节点的最小子树:找到一个深度尽可能大的节点,这个节点的孩子或孩子的孩子中包含全部的最深节点


举个栗子

输入:



输出:节点2
因为最深的节点是7和4,包含7和4的最小的子树是2

输入:


输出:节点1
因为最深的节点是4、5和6,全部包含4、5和6的节点只有1节点了,所以结果为节点1

输入:



输出:节点6

思路

一般涉及到树的问题都可以尝试用递归来解决,递归的核心就是递归函数的设计了,递归函数的语义一定要设计好,不然会递归得云里雾里
这里设计一个递归函数,其语义就是求出一棵树中包含所有最深节点的最小子树,即
输入:一棵树
输出:这棵树中包含所有最深节点的最小子树的根节点(简称包最小

简单粗暴的方法才是好方法——鲁迅


于是递归函数就这样写:

fun subtreeWithAllDeepest(root: TreeNode?):TreeNode?

但是转念一想,如果一个节点有 left 和 right ,并调用这个递归函数得到 left 和 right 的递归结果,怎么比较两个结果哪个才是我想要的呢?
于是我们在返回值中加入一个参数:输入的节点中最大深度
于是改进递归函数:

fun subtreeWithAllDeepest(root: TreeNode?):Result

class Result(var node: TreeNode?, var depth: Int)//递归返回结果,node是当前树中包含所有最深节点的最大子树根节点,depth是当前树的最大深度

要求出根节点代表的树的包最小,那么先求出左子树的包最小和右子树的包最小,假设左右子树的递归结果为 L 和 R ,如果 L.depth>R.depth,则说明包最小在 left 中,此时应该返回左子树的递归结果,但是应该将结果中的depth加1,因为最大深度还要算上当前节点,即:
Result(node=L.node , depth=L.depth+1)

如果L.depth<R.depth,则返回:
Result(node=R.node , depth=R.depth+1)

如果L.depth==R.depth,则说明左右子树中都有最大深度节点,此时的最小子树就是当前节点,此时返回:
Result(node=currentNode , depth=L.depth+1)
最后Result中的node节点就是要求的节点

举个例子来说明递归过程:
以上面第2个例子为例,递归过程如下:

  • 求节点1这颗树的包最小
  • 1发现有 left 和 right,于是把锅甩给 2 和 3,分别问 2 的包最小和 3 的包最小
  • 2把锅甩给4和5,3 把锅甩给 6
  • 4和5发现自己是叶子节点,叶子节点的包最小即它自己,于是返回了Result(node=4,depth=1)和Result(node=5,depth=1)
  • 2收到4和5的返回结果,发现depth都为1,这说明4和5中都有最深的节点,那么2就是包含这些所有最深节点的最小子树了,于是返回Result(node=2,depth=2)
  • 6返回Result(node=6,depth=1)
  • 3没有左子树,所以左子树递归结果为Result(node=null,depth=0),收到6返回结果后发现其depth>0,所以返回Result(node=6,depth=2)
  • 1收到2和3的结果,发现depth都是2,说明2和3的子树中都存在最深节点,所以1返回Result(node=1,depth=3)

递归结束:最后结果为Result(node=1,depth=3)
最终返回:node=1

实现

    //递归函数
    fun subtreeWithAllDeepest(node: TreeNode?): Result {
        if (node == null) {
            return Result(null, 0)
        }
        var l = subtreeWithAllDeepest(node.left)//求出左子树的递归结果
        var r = subtreeWithAllDeepest(node.right)//求出右子树的递归结果
        if (l.depth > r.depth) {//如果左子树的最大深度大于右子树,则应该返回左子树中包含所有最深结点的最小子树节点
            l.depth++
            return l
        } else if (l.depth < r.depth) {//如果右子树的最大深度大于左子树,则应该返回右子树中包含所有最深结点的最小子树节点
            r.depth++
            return r
        } else {//如果左右相等,则说明左右子树中都包含有最深节点,那当前节点就是包含所有最深结点的最小子树节点
            l.node = node
            l.depth++
            return l
        }
    }

//递归结果保存类,node代表当前树中包含所有最深结点的最小子树节点,depth代表当前树的最大深度
class Result(var node: TreeNode?, var depth: Int)

相关文章

  • 每日算法题—包含所有最深结点的最小子树

    题目描述 给定一棵二叉树,求包含所有最深节点的最小子树最深节点:深度最大的节点,深度即当前节点到根节点的最短距离包...

  • 二叉树三种遍历的实现(递归)

    前序递归遍历算法:访问根结点-->递归遍历根结点的左子树-->递归遍历根结点的右子树 中序递归遍历算法:递归遍历根...

  • 二叉查找(排序)树的剑指Offer算法

    特性: 如左子树不空,则左子树上所有结点均小于根结点的值 如右子树不空,则右子树上所有结点均大于根结点的值 左右子...

  • 京东

    树中任何结点的左子树中所有结点的值均比该结点小,右子树中所有结点的值均比该结点大。

  • 树(四)

    1. 定义 2. 基本术语 2.1 树结点:包含一个数据元素及若干指向子树的分支;2.2 孩子结点:结点的子树的根...

  • 二叉查找树(二叉排序树)

    左子树上所有结点的数据域均小于或等于根结点的数据域,右子树上所有结点的数据域均大于根结点的数据域 查找操作: 由于...

  • Leetcode 865. 具有所有最深结点的最小子树(后序遍历

    问题描述 给定一个根为 root 的二叉树,每个结点的深度是它到根的最短距离。如果一个结点在整个树的任意结点之间具...

  • 数据结构笔记(树->堆)

    堆(heap):结构性:用数组表示的完全二叉树有序性:任一结点的关键字是其子树所有结点的最大值(最小值),从根结点...

  • 判断二叉树的子树&子结构(C++)

    判断二叉树B是否是二叉树A的子树或子结构。 定义区别 子树:若B是A的子树,则A包含B的所有结点,并且B的叶子节点...

  • 二叉树、平衡树、红黑树

    二叉查找树 左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它的根结点的值。左、右...

网友评论

      本文标题:每日算法题—包含所有最深结点的最小子树

      本文链接:https://www.haomeiwen.com/subject/ipespctx.html