(平衡二叉树判断是否为AVL树）leetcode110

平衡二叉树（avl)树意思是左右子树的最高深度相减<=0也就是abs(left - right) <=0

至于深度用index dfs的标记法来做

为什么用遍历用前序遍历？

答：因为判断左右子树，只能在具有左右子树的父结点来进行

只要有一课子树不满足条件那就不是avl树

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { bool check=true; int bracktring(int index,TreeNode *root) { if(root==nullptr) return index; int left= bracktring(index+1,root->left); int right=bracktring(index+1,root->right); if (abs(left - right) > 1) {//核心代码 check = false; } return max(left,right); } public: bool isBalanced(TreeNode* root) { int index=1; bracktring(index,root); return check; } };