[LintCode/LeetCode] Balanced Binary Tree

morgan 發布于2019-08-14 15:33 / 1568人閱讀

摘要：根據二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數。在主函數中，利用比較左右子樹的差值來判斷當前結點的平衡性，如果不滿足則返回。

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.

Example

Given 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

根據二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數depth()。在主函數中，利用比較左右子樹depth的差值來判斷當前結點的平衡性，如果不滿足則返回false。然后遞歸當前結點的左右子樹，得到結果。

Solution

public 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;
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree Balanced Binary

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65851.html

[LintCode/LeetCode] Binary Tree Pruning

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...

rockswang 2019-08-16 12:37 評論0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了幾道二分法的題目練手，發現這道題已經淡忘了，記錄一下。這道題目的要點在于找的區間。邊界條件需要注意若或數組為空，返回空當前進到超出末位，或超過，返回空每次創建完根節點之后，要將加，才能進行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

馬忠志 2019-08-14 15:40 評論0 收藏0
[LintCode/LeetCode] Binary Tree Maximum Path Sum

摘要：調用函數更新路徑和的最大值，而函數本身需要遞歸，返回的是單邊路徑和。所以函數要返回的是，主函數中返回的卻是最上一層根節點處和的較大值，與之前遍歷過所有路徑的最大值之間的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...

cnTomato 2019-08-14 15:34 評論0 收藏0
[LintCode/LeetCode] Binary Tree Zigzag Level Orde

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...

AlphaGooo 2019-08-14 15:40 評論0 收藏0
[LintCode/LeetCode] Binary Tree InOrder Traversal

摘要：遞歸法不說了，棧迭代的函數是利用的原理，從根節點到最底層的左子樹，依次入堆棧。然后將出的結點值存入數組，并對出的結點的右子樹用函數繼續迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

tomorrowwu 2019-08-14 15:39 評論0 收藏0