> 文档中心 > 力扣刷题之平衡二叉树

力扣刷题之平衡二叉树

                                      Welcome to you每日一刷系列


平衡二叉树

递归

迭代


平衡二叉树

 

思路:一打眼看这道题很像前面我做的那个二叉树的最大深度 ,不过还是很有区别的。这里我们先看一个概率:就是高度和深度的区别:

高度:指从根节点到该节点的最长简单路径边的条数。

深度:指从根节点到该节点的最长简单路径边的条数。

求二叉树的深度我们用前序遍历,边遍历边记录深度,当然那道题也能用后序遍历做,求出来的高度正好也是其最大深度,具体代码看我那篇博客.那么这道题也要用自顶而下前序遍历的方法做吗?当然是可以做的,不过需要递归遍历这棵树的所有节点,如果对每个节点都算一遍最大深度,时间复杂度是比较高的。

所以最好的解法是反过来思考,只计算一次最大深度,计算的过程中在后序遍历位置顺便判断二叉树是否平衡:

递归

1.明确递归的返回值和参数

参数:传入当前的节点;

返回值:以当前传入节点为根节点的树的高度。

那么到底返回什么值才能判断他是否是平衡二叉树囊?

如果当前传入的值不是平衡二叉树我们直接返回-2(任意规定一个数),如果是平衡二叉树我们就返回当前根节点的树的高度

int _isBalanced(TreeNode* node)

2.明确终止条件

递归的过程中依然是遇到空节点了为终止,返回0,表示当前节点为根节点的树高度为0

      if(node==nullptr) {     return 0; }

3明确单层循环逻辑

判断当前左右子树的差值,如果差值大于1,说明已经不是平衡二叉树,返回-2,如果小于等于

1,则返回当前树的高度.

int result=0;int leftnum=_isBalanced(node->left);//左if(leftnum==-2) return -2;int rightnum=_isBalanced(node->right);//右if(rightnum==-2)return -2;if(abs(leftnum-rightnum)>1)//当前左右节点大于1{    result=-2;}else{   result=1+max(leftnum,rightnum);//中}return result;

代码: 

class Solution {public:    int _isBalanced(TreeNode* node)    { if(node==nullptr) {     return 0; } int result=0;int leftnum=_isBalanced(node->left);if(leftnum==-2) return -2;int rightnum=_isBalanced(node->right);if(rightnum==-2)return -2;if(abs(leftnum-rightnum)>1){    result=-2;}else{   result=1+max(leftnum,rightnum);}return result;    }    bool isBalanced(TreeNode* root) { return _isBalanced(root)==-2?false:true;//判断返回的值是否是-2    }};

迭代

这道题不建议使用迭代,效率很低,并且也不是很好理解.通过栈模拟的后序遍历找每一个节点的高度(其实是通过求传入节点为根节点的最大深度来求的高度)。

class Solution {private:    int getDepth(TreeNode* cur) { stack st; if (cur != NULL) st.push(cur); int depth = 0; // 记录深度 int result = 0; while (!st.empty()) {     TreeNode* node = st.top();     if (node != NULL) {  st.pop();  st.push(node);     // 中  st.push(NULL);  depth++;  if (node->right) st.push(node->right);  // 右  if (node->left) st.push(node->left);    // 左     } else {  st.pop();  node = st.top();  st.pop();  depth--;     }     result = result > depth ? result : depth; } return result;    }public:    bool isBalanced(TreeNode* root) { stack st; if (root == NULL) return true; st.push(root); while (!st.empty()) {     TreeNode* node = st.top();  // 中     st.pop();     if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {  return false;     }     if (node->right) st.push(node->right);    // 右(空节点不入栈)     if (node->left) st.push(node->left);      // 左(空节点不入栈) } return true;    }};