leetcode 110. Balanced Binary Tree（平衡二叉树的判断） DFS深度优先遍历

淩亂°似流年 2022-06-08 03:16 176阅读 0赞

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

本题考查的是平衡二叉树的判断，平衡二叉树是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，那么直接递归判断即可。

1） 递归判断二叉树是否是平衡二叉树

2） 递归找二叉树高度,求高度也是用递归

代码如下：

/*class TreeNode 
    {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    
     /*
      *   平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1
      *   1.递归判断二叉树是否是平衡二叉树
      *   2.递归找二叉树高度,求高度也是用递归
      *   递归停止条件：
      *   递归到叶子节点时终止，root==null时，返回0。
      */
    
    public class Solution
    {
        public boolean isBalanced(TreeNode root) 
        {
            if(root ==null)
                return true;
    
            int heightLeft=getHeight(root.left);
            int heightRight=getHeight(root.right);
            if(Math.abs(heightLeft-heightRight)<=1)
                return isBalanced(root.left) && isBalanced(root.right);
            else
                return false;
        }
    
        int getHeight(TreeNode root) 
        {
            if(root==null)
                return 0;
            else
            {
                int heightLeft=getHeight(root.left)+1;
                int heightRight=getHeight(root.right)+1;
                return Math.max(heightLeft, heightRight);
            }
        }
    }

下面是C++的做法，就是一个简单的DFS深度优先遍历的应用

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    
    using namespace std;
    
    /*
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        bool isBalanced(TreeNode* root) 
        {
            if (root == NULL)
                return true;
            else
            {
                int left = getHeight(root->left) + 1;
                int right = getHeight(root->right) + 1;
                if (abs(left - right) <= 1)
                    return isBalanced(root->left) && isBalanced(root->right);
                else
                    return false;
            }
    
        }
    
        int getHeight(TreeNode* root)
        {
            if (root == NULL)
                return 0;
            else
            {
                int left = getHeight(root->left) + 1;
                int right = getHeight(root->right) + 1;
                return max(left, right);
            }
        }
    };