据结构与算法(八) 二叉树的练习
练习
一、计算二叉树高度
递归
相当于求根节点的高度 根节点高度等于1+子节点最高的高度
public int height() {
return height(root);
}
private int height(Node<E> node) {
if (node == null) {
return 0;
}
return 1 + Math.max(height(node.left), height(node.right));
}迭代
利用层序遍历
•设定levelSize初始值为1（只有一个根节点）•当进行while循环的时候 levelsize-- 操作。因为levelSize和每层节点个数相等。所以当levelSize为0的时候，下一个levelSize的大小就等于此时在队列中的元素个数。•当levelSize== 0的时候 •进行赋值下一层的个数 levelSize = queue.size()•此时代表一个层级遍历结束 height++
代码如下图所示
public int height() {
if (root == null) {
return 0;
}
int height = 0;
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if(node.left != null) {
queue.offer(node.left);
}
if(node.right!= null) {
queue.offer(node.right);
}
if (levelSize == 0) {
levelSize = queue.size();
height ++;
}
}
return height;
}二、判断一颗树是否为完全二叉树
层序遍历
思路
while(队列不为空) {
如果标记为叶子节点 判断是否为叶子节点，如果不是返回false
•Left •如果left ！= null 入队•如果left == null •如果right != null 返回false；•Right•如果right != null 入队•标记其余都是叶子节点
}
•当层序遍历结束后返回true；
private boolean isCompleteTree(Node<E> root) {
Queue<Node<E>> queue = new LinkedList<Node<E>>();
queue.offer(root);
boolean leaf = false;
while (queue.size() != 0) {
Node<E> node = queue.poll();
if (leaf) {
if (!node.leaf()) {
return false;
}
}
if (node.left != null) {
queue.offer(node.left);
}else {
if (node.right != null) {
return false;
}
}
if (node.right != null) {
queue.offer(node.right);
}else {
leaf = true;
}
}
return true;
}三、翻转二叉树
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
##### 输出：
4
/ \
7 2
/ \ / \
9 6 3 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解题思路
利用遍历翻转
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode tempNode = root.left;
root.left = root.right;
root.right = tempNode;
invertTree(root.left);
invertTree(root.right);
return root;
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-10-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录