时间:2021-05-19
面试的时候碰到一个题:如何找到一个二叉树最远的叶子结点,以及这个叶子结点到根节点的距离?
第一反应肯定是递归
如何能找到最远的叶子结点,同时也能记下这个叶子节点到根节点的距离呢?采用一个List保持从根节点到叶子节点的路径就可以了,这个list的长度-1就是叶子结点到根节点的距离,list的最后一个结点就是到叶子结点
二叉树我就不用设计了,具体代码参见我的另一篇文章
/** * 寻找最远的叶子节点 */ public void findFarestLeaf() { List<Node> path = new ArrayList<Node>(); List<Node> longestPath = findLongestPath(root, path); Node leaf = longestPath.get(longestPath.size() - 1); System.out.println("最远的叶子节点是<" + leaf.key + ", " + leaf.value + ">,到根节点的距离是:"+(longestPath.size() - 1)); } public List<Node> findLongestPath(Node x, List<Node> path) { if (x == null) return path; // 每次递归必须新建list,要不然会导致递归分支都在同一个list上面做,实际是把所有结点都加入这个list了 List<Node> currPath = new ArrayList<Node>(); currPath.addAll(path); currPath.add(x); List<Node> leftPath = findLongestPath(x.left, currPath); List<Node> rightPath = findLongestPath(x.right, currPath); if (leftPath.size() > rightPath.size()) return leftPath; else return rightPath; }以上这篇寻找二叉树最远的叶子结点(实例讲解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
提出问题:翻转一棵二叉树。(除根结点以外)原始二叉树:新二叉树:解题思路:遇见二叉树先想到递归。从最下层的叶子结点开始置换左右子节点,一直置换到到最上层的根结点
一.背景介绍:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmanTree)。哈夫曼
问题提出:给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:叶子节点是指没有子节点的节点。解决思路:递归法求解。从根
问题如何遍历一个二叉树遍历二叉树就是访问二叉树的每一个节点二叉树父结点下先左访问,先序遍历(根左右)例如:遍历以下的二叉树遍历结果:ABDECFPython代码
一哈夫曼树以及文件压缩原理:1.哈夫曼树:给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树