Binary tree judgment

判断完全二叉树

思路

使用层序遍历的思想

• 遇到节点左为空且右不为空，则不是

• 遇到一个叶子节点，其后必全是叶子节点，否则不是

实现

bool isCBT(Node* root)
{if(root != null){queue<Node*> Nodeque;Nodeque.push(root);bool leaf = false;while(!Nodeque.empty()){Node* Front = Nodeque.front();Nodeque.pop();/******遇到子节点后，后续必全是子节点******/if(leaf && (Front->left != null || Front->right != null)){return false;}/******左为空，又不为空，不是完全二叉树******/if(Front->left == null&&Front->right != null){return false;}if(Front->left) Nodeque.push(Front->left);if(Front->right) Nodeque.push(Front->right);/******遇到第一个子节点******/if(!Front->left && !Front->right) leaf = true;}}return true;
}

判断搜索二叉树

数据

使用preValue表示左子树最后处理的数

思路

• 使用中序遍历的思想

• 比较preValue和root->value

实现

static int preValue = -1;
bool isSBT(Node* root)
{if(root == null) return true;bool isSBTleft = isSBT(root->left);if(!isSBTleft) return false;if(root->value <= preValue) return false;preValue = root->value;return isSBT(root->right);
}

总结

需要结合这两种二叉树的特性进行判断，考验对其结构的理解