劍指Offer系列(java版,詳細解析)55.二叉樹的深度

程序員社區 2022-01-08 04:42:37 阅读数:103

offer 系列 java 解析 二叉

題目一

題目描述

二叉樹的深度

輸入一顆二叉樹的根節點,求該樹的深度。從根節點到葉節點依次經過的節點(含根、葉節點)形成樹的一條路徑,最長路徑的長度為樹的深度。

二叉樹的節點定義如下:

測試用例

  • 功能測試(輸入普通的二叉樹;二叉樹中所有節點都沒有左/右子樹)
  • 特殊輸入測試(二叉樹只有一個節點;二叉樹的頭節點為空指針)

解題思路

遞歸思路

一個樹的深度可以理解為左、右子樹深度的最大值加1。

參考解題

/** * 二叉樹的深度 * */public class Solution1 {
 /** * 遞歸 * @param root * @return */ public int treeDepth(BinaryTreeNode root) {
 if (root == null) {
 return 0; } int left = treeDepth(root.left); int right = treeDepth(root.right); return Math.max(left, right) + 1; }}

題目二

平衡二叉樹

輸入一顆二叉樹的根節點,判斷該樹是不是平衡二叉樹。如果某二叉樹任意節點的左、右子樹的深度相差不超過1,那麼它就是一顆平衡二叉樹。

測試用例

  • 功能測試(輸入普通的二叉樹;不是平衡的二叉樹;二叉樹中所有節點都沒有左/右子樹)
  • 特殊輸入測試(二叉樹只有一個節點;二叉樹的頭節點為空指針)

解題思路

利用樹的深度來判斷

參考解題思想是樹的後序遍曆(從下到上)。在每個節點記錄它的深度,如果不平衡,則記錄該節點的深度為-1。

參考解題

/** * 二叉平衡樹 * */public class Solution3 {
 /** * 判斷是否為二叉平衡樹 * @param root * @return */ public boolean isBalanced_Solution(BinaryTreeNode root) {
 if (root == null) {
 return true; } return treeDepth(root) != -1; } /** * 樹的深度(後序遍曆) * * @param root * @return -1:錶示不是二叉平衡樹 */ public int treeDepth(BinaryTreeNode root) {
 if (root == null) {
 return 0; } int left = treeDepth(root.left); if (left == -1) {
 return -1; } int right = treeDepth(root.right); if (right == -1) {
 return -1; } if (Math.abs(left - right) > 1) {
 return -1; } else {
 return Math.max(left, right) + 1; } }}

題目考點

  • 考察應聘者對二叉樹的理解和編程能力。
  • 考察應聘者對新概念(樹的深度)的學習能力。
  • 考查應聘者的知識遷移能力。
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080442367311.html