本文共 2319 字,大约阅读时间需要 7 分钟。
原文地址:
已知一个二叉树,求它的高。空树的树高是0,下面的树的树高是3。
递归地计算一个节点的左右子树的树高,将高度设值为两个孩子最大高度加1。看下面的伪代码和程序的详细情况。
算法:
maxDepth()1. 如果树为空,那么返回02. 否则 (a) 递归得到左子树的最大高度 例如,调用maxDepth( tree->left-subtree) (b) 递归得到右子树的最大高度 例如,调用maxDepth( tree->right-subtree) (c) 对于当前节点,取左右子树高度的最大值并加1。 max_depth = max(左子树的最大高度, 右子树的最大高度) + 1 (d) 返回max_depth
下图是对于上面树的例子更清楚地说明了递归函数maxDepth()的执行。
maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1 = 2 + 1 / \ / \ / \ / \ / \ maxDepth('1') maxDepth('3') = 1= max(maxDepth('4'), maxDepth('5')) + 1= 1 + 1 = 2 / \ / \ / \ / \ / \ maxDepth('4') = 1 maxDepth('5') = 1
实现:
// Java program to find height of tree// A binary tree nodeclass Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }}class BinaryTree { Node root; /* Compute the "maxDepth" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int maxDepth(Node node) { if (node == null) return 0; else { /* compute the depth of each subtree */ int lDepth = maxDepth(node.left); int rDepth = maxDepth(node.right); /* use the larger one */ if (lDepth > rDepth) return (lDepth + 1); else return (rDepth + 1); } } /* Driver program to test above functions */ public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); System.out.println("Height of tree is : " + tree.maxDepth(tree.root)); }}// This code has been cpontributed by Mayank Jaiswal(mayank_24)
时间复杂度: O(n) 。