C/C++教程

Leetcode_110.平衡二叉树

本文主要是介绍Leetcode_110.平衡二叉树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：

从底部向上递归高度，若为空节点则返回0，否则返回左右孩子的最大高度+1。再进行高度检查即可，若子树高度差大于1则设置 flag 为 false ，直接退出即可。

递归基：遇到空节点，返回0；

AC代码：(ps.这种递归还是有点耗费空间。。)

bool flag = 1;
    unsigned check(TreeNode const *root)
    {
        if (!flag || !root)
            return 0;
        int ld = check(root->left), rd = check(root->right);
        if (ld - rd > 1 || rd - ld > 1)
        {
            flag = 0;
            return 0;
        }
        else
            return 1 + (ld >= rd ? ld : rd);
    }
    bool isBalanced(TreeNode *root)
    {
        check(root);
        return flag;
    }

 

这篇关于Leetcode_110.平衡二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航