平衡二叉树
二叉树的深度：从根节点往下查到叶子节点
二叉树的高度：从叶子节点往上查到根节点
求二叉树的深度和高度
深度：前序遍历
- 深度从根节点往下找，在递归栈增加的时候计算
高度：后序遍历 - 高度从叶子节点网上找，在递归栈减少的时候计算
/** * 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 { public: //计算树的高度，后序遍历。当不是平衡二叉树（左右子树高度最多差1）的时候返回-1 int get_tree_height(TreeNode* cur) { if(cur==nullptr) return 0; int left_height = get_tree_height(cur->left); if(left_height == -1) return -1;//如果左子树不是平衡二叉树，整个树也不是平衡二叉树 int right_height =get_tree_height(cur->right); if(right_height == -1) return -1;//如果右子树不是平衡二叉树，整个树也不是平衡二叉树 //两个子树是平衡二叉树，但是不确定整个树是不是平衡二叉树，计算两个树的高度差 //如果高度差大于1，则不是平衡二叉树。如果高度差是0或者1，则平衡二叉树的高度是最高子树加上根节点1 return abs(left_height - right_height) > 1 ? -1 : 1+max(left_height , right_height); } bool isBalanced(TreeNode* root) { if(root == nullptr) return true; return get_tree_height(root)== -1 ? false:true; } };
二刷
/** * 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 { public: int back_tark(TreeNode* cur) { if(cur == nullptr) return 0; int left_deep = back_tark(cur->left); int right_deep = back_tark(cur->right); if(left_deep==-1||right_deep==-1) return -1; if( abs(left_deep - right_deep) <= 1) return max(left_deep,right_deep)+1; else return -1; } bool isBalanced(TreeNode* root) { if(root==nullptr) return true; if(back_tark(root) == -1) return false; else return true; } };
