判断二叉树是不是平衡二叉树(Java)

时间：2021-11-04 17:31:42

题目

  • 输入一棵二叉树的根节点，判断该树是不是平衡的二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

解法

重复遍历多次的解法

  • 这种解法是建立在前文中描述的求解二叉树的深度的基础上实现的。在遍历二叉树的每个节点的过程中，通过求取当前节点的左右子树深度判断，只有当左右节点的左右子树的深度相差都不超过1时，这颗二叉树才是平衡二叉树。

每个节点只遍历一次节点

  • 剑指offer中给出了一种每个节点都只遍历一次的解法，通过采用后序遍历的方式，依次遍历每个节点，并判断是不是平衡二叉树，其实现代码如下。不过其实现代码是针对c++，能够正常运行在C++的编译器中；但是由于Java和C++之间的差别（对于基本数据类型只是按值传递），因此并不能正确的运用到Java的编译器中。
bool IsBalanced(BinaryTreeNode* pRoot, int* depth)  
{  
if(pRoot== NULL)  
    {  
        *depth = 0;  
return true;  
    }  

int nLeftDepth,nRightDepth;  
bool bLeft= IsBalanced(pRoot->m_pLeft, &nLeftDepth);  
bool bRight = IsBalanced(pRoot->m_pRight, &nRightDepth);  

if (bLeft && bRight)  
    {  
int diff = nRightDepth-nLeftDepth;  
if (diff<=1 || diff>=-1)  
        {  
            *depth = 1+(nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);  
return true;  
        }  
    }  

return false;  
}  

bool IsBalanced(BinaryTreeNode* pRoot)  
{  
int depth = 0;  

return IsBalanced(pRoot, &depth);  
}

适用于Java的只遍历一次节点的解法

  • 借鉴剑指offer中的第二种实现，再结合Java的自身特性，我们通过在返回值上做文章，使得在遍历每个节点的过程中能够统计到各子树是不是平衡二叉树，进而判断出整颗二叉树的情况。其思想是采用类似于后序遍历的形式，对每个节点进行递归遍历。同时在遍历过程中统计各节点子树的深度，若深度满足平衡二叉树的要求，则将深度返回至上层；若深度不满足平衡二叉树的要求，则通过返回-1值来表明整颗树都不再是平衡二叉树，结束各节点的递归遍历。

Java实现


import java.util.Scanner;

public class DepthOfBinaryTree
{
private static Scanner sc = new Scanner(System.in);

static class BinaryTree
    {
int item;
        BinaryTree left;
        BinaryTree right;
    }

public static int depthOfBinaryTree(BinaryTree root)
    {
if (null == root)
        {
return 0;
        }

int left = 0, right = 0;
if (root.left != null)
        {
            left = depthOfBinaryTree(root.left);
        }
if (root.right != null)
        {
            right = depthOfBinaryTree(root.right);
        }

return ((left > right) ? left : right) + 1;
    }

// 重复多次遍历节点
public static boolean isBanlancedTree(BinaryTree root)
    {
if (null == root)
        {
return false;
        }

int left = depthOfBinaryTree(root.left);
int right = depthOfBinaryTree(root.right);

int diff = Math.abs(left - right);

if (diff > 1)
        {
return false;
        }

return isBanlancedTree(root.left) && isBanlancedTree(root.right);
    }

// 从叶节点开始判断，不会重复遍历节点
public static boolean isBalanceTreeAno(BinaryTree root)
    {
if (null == root)
        {
return false;
        }
int index = isBalanceTreeMid(root);
return (index != -1);
    }
private static int isBalanceTreeMid(BinaryTree root)
    {
if (null == root)
        {
return 0;
        }

int left = 0, right = 0;
if (root.left != null)
        {
            left = isBalanceTreeMid(root.left);
        }
if (left != -1  && root.right != null)
        {
            right = isBalanceTreeMid(root.right);
        }
if (left != -1 && right != -1)
        {
int diff = Math.abs(left - right);
if (diff <= 1)
            {
return ((left > right) ? left : right) + 1;
            }
        }
return -1;
    }

public static BinaryTree createTree(BinaryTree bt)
    {   
        System.out.println("Please Enter: ");
        String line = sc.nextLine();
if ("0".equals(line))
        {
            bt = null;
        }
else
        {
            bt.item = Integer.valueOf(line);

            BinaryTree left = new BinaryTree();
            BinaryTree right = new BinaryTree();
            bt.left = createTree(left);
            bt.right = createTree(right);
        }

return bt;
    }

public static void foreachNode(BinaryTree bt)
    {
if (null == bt)
        {
return ;
        }
        System.out.print(bt.item + " ");
if (bt.left != null)
        {
            foreachNode(bt.left);
        }
if (bt.right !=null)
        {
            foreachNode(bt.right);
        }
    }

public static void close()
    {
if (sc != null)
        {
            sc.close();
        }
    }

public static void main(String [] args)
    {
        DepthOfBinaryTree.BinaryTree tree = new DepthOfBinaryTree.BinaryTree();

        tree = createTree(tree);
        close();
        foreachNode(tree);
        System.out.println();

        System.out.println(depthOfBinaryTree(tree));

        System.out.println("isBalance = " + isBalanceTreeAno(tree));
    }
}
  • 说明
    代码中给出了判断二叉树是否是平衡二叉树的两种实现方式，并给出了二叉树的创建以及中序遍历实现，便于在测试过程中创建二叉树以及观察数据。
  • 测试
    以下是对剑指offer中给出的二叉树进行的测试：
Please Enter: 
1
Please Enter: 
2
Please Enter: 
4
Please Enter: 
0
Please Enter: 
0
Please Enter: 
5
Please Enter: 
7
Please Enter: 
0
Please Enter: 
0
Please Enter: 
0
Please Enter: 
3
Please Enter: 
0
Please Enter: 
6
Please Enter: 
0
Please Enter: 
0
1 2 4 5 7 3 6 
4
isBalance = true
标签：

相关文章