平衡二叉树

weblog 206 0 0

leetcode110题(简单)

原链接 https://leetcode-cn.com/problems/balanced-binary-tree/

题目描述

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例1
案例

输入:root = [3,9,20,null,null,15,7]输出:true

示例2
案例

输入root = [1,2,2,3,3,null,null,4,4]输出false

解题思路

递归,分治。

递归遍历二叉树所有节点,从叶子节点开始向上判断每个节点所在的子树,是否是平衡二叉树。直到树的根节点为平衡二叉树结束。

代码(java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return b;
    }
    boolean b=true;
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }else{
            int left=dfs(root.left);
            if(!b){
                return 0;
            }
            int right=dfs(root.right);
            //System.out.println(Math.abs(left-right));
            if(Math.abs(left-right)<=1){
                return (left>right?left:right)+1;
            }else{
                b=false;
                return 0;
            }
        }
    }
}

 

猜你喜欢
数据结构与算法 2140 packageavlTree;importjava.util.LinkedList;/***avl)*@authorAdministrator**/publicclassAvlTree
official 183 和一个head为第一个节点的链表。如果在中,存在一条一直向下的路径,且每个点的数值恰好一一对应以head为首的链表中每个节点的值,那么请你返回True,否则返回False。一直向下的路径的意思
数据结构与算法 3231 在关于的多种算法中都用到了的旋转来使保持相对,比如avl,红黑等...1.的左旋(pivot为旋转中心点)2.来个动图3.代码演示:/** *左旋 *p为旋转的中心点
数据结构与算法 6348 题目:判断下方两棵右方的是否为左方的子例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 3289 avl:AVL本质上是一颗查找1.avl的性质左子和右子的高度之差的绝对值不超过1中的每个左子和右子都是AVL每个节点都有一个因子(balancefactor--bf
数据结构与算法 4036 基本操作c++classnode{public: intdata; node*left; node*right; node(); node(intdata); node(intdata
official 206 leetcode第257题(简单)原链接:https://leetcode-cn.com/problems/binary-tree-paths/题目描述给定一个,返回所有从根节点到叶子节点的路
数据结构与算法 2009 删除节点c++先看一个简单的图删除节点是分以下几种情况:1.待删节点为叶子节点:此种情况下直接删除叶子节点即可2.待删节点只有左子,或只有右子,那么将左子或右子的根节点替换该节点即可
目录
祝愿神州十三飞行乘组平安归来