判断二叉树是否为平衡二叉树,将java代码翻译为c++,c
public class IsBalancedTree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static class Info{
public boolean isBalanced;
public int height;
public Info(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
public static boolean isBalancedTree(Node head){
return process(head).isBalanced;
}
/*
* 平衡二叉树
* 向左树要信息,像右树要信息,当前节点解析处理返回
*/
private static Info process(Node head){
if (head == null) {
return new Info(true, 0);
}
Info leftInfo = process(head.left);
Info rightInfo = process(head.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isBalanced = leftInfo.isBalanced &&
rightInfo.isBalanced &&
Math.abs(leftInfo.height - rightInfo.height) < 2;
return new Info(isBalanced, height);
}
}
把Node类转换为结构体,或者类都可以,再定义头结点作为链表名称。
#include <cstdio>
#include <stack>
#include <iostream>
#include <queue>
#include <map>
#include <windows.h>
#define MaxSize 100
//#define max(a, b) ( ( (a) > (b) ) ? a : b )
using namespace std;
typedef struct Node
{
int value;
struct Node* left, * right;
}Node,*BiTree;
typedef struct Info
{
Info(bool b, int h)
{
isBalanced = b;
height = h;
}
bool isBalanced;
int height;
}Info;
Info* process2(BiTree head) {
if (head == NULL)
{
return new Info(true, 0);
}
Info* leftInfo = process2(head->left);
Info* rightInfo = process2(head->right);
int height = max(leftInfo->height, rightInfo->height) + 1;
bool isBalanced = leftInfo->isBalanced && rightInfo->isBalanced &&
abs(leftInfo->height - rightInfo->height) < 1;
Info* info = new Info{ isBalanced , height };
return info;
}
bool isBanlancedTree(BiTree head) {
Info *info = process2(head);
return info->isBalanced;
}