LeetCode : 110. Balanced Binary 平衡二叉树

一时失言乱红尘 2021-06-24 16:10 403阅读 0赞

试题
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 1:

Given the following tree [3,9,20,null,null,15,7]:

  1. 3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

Return true.

代码：
本质还是求解树的深度问题

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     boolean flag = true;
  12.     public boolean isBalanced(TreeNode root) {
  13.         findDepth(root);   
  14.         return flag;
  15.     }
  17.     public int findDepth(TreeNode root){
  18.         if(root==null) return 0;
  19.         int left = findDepth(root.left);
  20.         int right = findDepth(root.right);
  21.         if(Math.abs(left-right)>1) flag = false;
  22.         return Math.max(left,right)+1;
  23.     }
  24. }

发表评论

表情：
评论列表 （有 0 条评论，403人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LeetCode110. 平衡二叉树

    给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： > 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二

    快来打我*快来打我*/ 0 赞/ 271 阅读