专栏首页老沙课堂据结构与算法(八) 二叉树的练习

据结构与算法(八) 二叉树的练习

练习

一、计算二叉树高度

递归

相当于求根节点的高度 根节点高度等于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;
    }
}

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(五) 队列

    •先进先出原则(First In First Out) FIFO•队尾(rear):只能进行入队操作(enQueue)->添加元素•队头(front):只能进行...

    老沙
  • iOS读写安全

    给属性添加atomic 可以保证属性的setter和getter原子性操作,也就是保证setter和getter内部是线程同步的

    老沙
  • 数据结构与算法(二)数组

    在堆中连续开辟的一段空间,每个元素占有相同大小的空间。一经开辟,即固定大小,无法改变长短。

    老沙
  • 从Zookeeper 到 Elastic Job 的Simple Job使用(二)

    按理说,我赋值的是shardingparameter,但是结果确实jobparameter,因为我一开始使用了jobparameter,然后改成sharding...

    MickyInvQ
  • JavaScript小游戏2

    添加CSS样式 这类就没有定义外部的样式css文件,之间在页面中head->style标签中写入:

    Lemon黄
  • synchronized 关键字

    Synchronized 是 Java 中的一种锁的方式,是在 JVM 层面一种锁。在 jdk 1.6以前是一种重量级锁,在经历过优化后 Synchronize...

    付威
  • 小程序生成图片分享朋友圈

    小程序开发者都希望自己的小程序得以广泛传播,因为不少小程序都设计了很多转发激励行为,但分享小程序到朋友圈(或其他外部平台)一直是一个难题。一个常见但方案就是生成...

    用户1175156
  • 快速掌握并发编程---synchronized篇(下)

    昨天聊了Synchronized的部分知识点快速掌握并发编程---synchronized篇(上),今天,接着聊聊 Synchronized的其他重要知识点。

    田维常
  • 为Windows系统替换优雅的苹方,好看的OPPO字体

    自从坏了一台12寸的MacBook,我使用Windows的频率就升高了,但Windows的系统字体确实丑了些 。然后我找到了一个可以替换Windows系统字体为...

    zhaoolee
  • 系统安装部署系列教程(三):VHD方式安装系统

    版权声明:本文为博主原创文章,转载请注明出处。 ...

    乐百川

扫码关注云+社区

领取腾讯云代金券