資訊專欄INFORMATION COLUMN
摘要：根據(jù)二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹的差值來判斷當(dāng)前結(jié)點的平衡性，如果不滿足則返回。
Problem
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
ExampleGiven binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A) 3 B) 3
/
9 20 20
/ /
15 7 15 7
The binary tree A is a height-balanced binary tree, but B is not.
Note根據(jù)二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數(shù)depth()。在主函數(shù)中，利用比較左右子樹depth的差值來判斷當(dāng)前結(jié)點的平衡性，如果不滿足則返回false。然后遞歸當(dāng)前結(jié)點的左右子樹，得到結(jié)果。
Solutionpublic class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
if (Math.abs(depth(root.left)-depth(root.right)) > 1) return false;
return isBalanced(root.left) && isBalanced(root.right);
}
public int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right))+1;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65851.html
Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...
摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點之后，要將加，才能進行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...
摘要：調(diào)用函數(shù)更新路徑和的最大值，而函數(shù)本身需要遞歸，返回的是單邊路徑和。所以函數(shù)要返回的是，主函數(shù)中返回的卻是最上一層根節(jié)點處和的較大值，與之前遍歷過所有路徑的最大值之間的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...
Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...
摘要：遞歸法不說了，棧迭代的函數(shù)是利用的原理，從根節(jié)點到最底層的左子樹，依次入堆棧。然后將出的結(jié)點值存入數(shù)組，并對出的結(jié)點的右子樹用函數(shù)繼續(xù)迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...
閱讀 2616·2021-11-18 10:02
閱讀 2642·2021-11-15 11:38
閱讀 3723·2021-11-12 10:36
閱讀 712·2021-11-12 10:34
閱讀 2924·2021-10-21 09:38
閱讀 1506·2021-09-29 09:48
閱讀 1512·2021-09-29 09:34
閱讀 1104·2021-09-22 10:02
