【数据结构与算法】二叉树——平衡二叉树
2021-02-14 22:18
标签：数据结构与算法 return mat 数据 lag 一个 ref com problems LeetCode：平衡二叉 给定一个二叉树，判断它是否是高度平衡的二叉树。 使用实例域变量记录是否与有不满足平衡的节点出现，使用一次递归即可。 【数据结构与算法】二叉树——平衡二叉树 标签：数据结构与算法 return mat 数据 lag 一个 ref com problems 原文地址：https://www.cnblogs.com/buptleida/p/12718422.html平衡二叉树
题目描述：
示例：
给定二叉树 [3,9,20,null,null,15,7]
3
/ 9 20
/ 15 7
返回true
思想：
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private boolean flag = true;
//返回高度，并且在递归过程中记录flag
private int treeDepth(TreeNode root){
if(root ==null)
return 0;
int leftLen = treeDepth(root.left);
int rightLen = treeDepth(root.right);
if(Math.abs(leftLen-rightLen)>1)
flag = false;
return Math.max(leftLen,rightLen)+1;
}
public boolean isBalanced(TreeNode root) {
int i = treeDepth(root);
return flag;
}
}
文章标题：【数据结构与算法】二叉树——平衡二叉树
文章链接：http://soscw.com/index.php/essay/55369.html