专栏首页Python专栏【数据结构与算法】一起搞定面试中的二叉树(一)

【数据结构与算法】一起搞定面试中的二叉树(一)

作者:IOExceptioner

最近总结了一些数据结构和算法相关的题目,这是二叉树相关面试题的总结,是用java实现的,由于篇幅有限,因此分为两部分,这是第一部分总结。先上二叉树的数据结构:

class TreeNode{
    int val;
    //左孩子
    TreeNode left;
    //右孩子
    TreeNode right;
}

二叉树的题目普遍可以用递归和迭代的方式来解

1. 求二叉树的最大深度

int maxDeath(TreeNode node){
    if(node==null){
        return 0;
    }
    int left = maxDeath(node.left);
    int right = maxDeath(node.right);
    return Math.max(left,right) + 1;
}

2. 求二叉树的最小深度

int getMinDepth(TreeNode root){
    if(root == null){
        return 0;
    }
    return getMin(root);
}

int getMin(TreeNode root){
    if(root == null){
        return Integer.MAX_VALUE;
    }
    if(root.left == null&&root.right == null){
        return 1;
    }
    return Math.min(getMin(root.left),getMin(root.right)) + 1;
}

3. 求二叉树中节点的个数

int numOfTreeNode(TreeNode root){
    if(root == null){
        return 0;
    }
    int left = numOfTreeNode(root.left);
    int right = numOfTreeNode(root.right);
    return left + right + 1;
}

4. 求二叉树中叶子节点的个数

int numsOfNoChildNode(TreeNode root){
    if(root == null){
        return 0;
    }
    if(root.left==null&&root.right==null){
        return 1;
    }
    return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
}

5. 求二叉树中第k层节点的个数

int numsOfkLevelTreeNode(TreeNode root,int k){
    if(root == null||k<1){
        return 0;
    }
    if(k==1){
        return 1;
    }
    int numsLeft = numsOfkLevelTreeNode(root.left,k-1);
    int numsRight = numsOfkLevelTreeNode(root.right,k-1);
    return numsLeft + numsRight;
}

6. 判断二叉树是否是平衡二叉树

boolean isBalanced(TreeNode node){
    return maxDeath2(node)!=-1;
}

int maxDeath2(TreeNode node){
    if(node == null){
        return 0;
    }
    int left = maxDeath2(node.left);
    int right = maxDeath2(node.right);
    if(left==-1||right==-1||Math.abs(left-right)>1){
        return -1;
    }
    return Math.max(left, right) + 1;
}

7.判断二叉树是否是完全二叉树

boolean isCompleteTreeNode(TreeNode root){
    if(root == null){
        return false;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    boolean result = true;
    boolean hasNoChild = false;
    while(!queue.isEmpty()){
        TreeNode current = queue.remove();
        if(hasNoChild){
            if(current.left!=null||current.right!=null){
                result = false;
                break;
            }
        }else{
            if(current.left!=null&&current.right!=null){
                queue.add(current.left);
                queue.add(current.right);
            }else if(current.left!=null&&current.right==null){
                queue.add(current.left);
                hasNoChild = true;
            }else if(current.left==null&&current.right!=null){
                result = false;
                break;
            }else{
                hasNoChild = true;
            }
        }
    }
    return result;
}

8. 两个二叉树是否完全相同

boolean isSameTreeNode(TreeNode t1,TreeNode t2){
    if(t1==null&&t2==null){
        return true;
    }
    else if(t1==null||t2==null){
        return false;
    }
    if(t1.val != t2.val){
        return false;
    }
    boolean left = isSameTreeNode(t1.left,t2.left);
    boolean right = isSameTreeNode(t1.right,t2.right);
    return left&&right;
}

9. 两个二叉树是否互为镜像

boolean isMirror(TreeNode t1,TreeNode t2){
    if(t1==null&&t2==null){
        return true;
    }
    if(t1==null||t2==null){
        return false;
    }
    if(t1.val != t2.val){
        return false;
    }
    return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
}

10. 翻转二叉树or镜像二叉树

TreeNode mirrorTreeNode(TreeNode root){
    if(root == null){
        return null;
    }
    TreeNode left = mirrorTreeNode(root.left);
    TreeNode right = mirrorTreeNode(root.right);
    root.left = right;
    root.right = left;
    return root;
}

11. 求两个二叉树的最低公共祖先节点

TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){
    if(findNode(root.left,t1)){
        if(findNode(root.right,t2)){
        return root;
        }else{
            return getLastCommonParent(root.left,t1,t2);
        }
    }else{
        if(findNode(root.left,t2)){
            return root;
        }else{
        return getLastCommonParent(root.right,t1,t2)
        }
    }
}
    // 查找节点node是否在当前 二叉树中
boolean findNode(TreeNode root,TreeNode node){
    if(root == null || node == null){
        return false;
    }
    if(root == node){
        return true;
    }
    boolean found = findNode(root.left,node);
    if(!found){
        found = findNode(root.right,node);
    }
    return found;
}

本文分享自微信公众号 - Python专栏(xpchuiit),作者:上海小胖

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

原始发表时间:2018-10-01

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • GitHub宕机24小时,我们还能干嘛

    不过我更喜欢下面这幅图,虽然我已经2年不用windows了,但是看到这个图还是很想笑啊,每次windows一个补丁,就能让你半天不用看屏幕了。

    用户1634449
  • 继万字谏言后,Python Web 怎么学,看这篇就够了!

    之前那篇「万字谏言,给那些想学Python的人,建议收藏后细看!」得到很多后台读者的留言,表示想再来点,甚至说万字系?你知道万字有多少么?不要杠我根本没有万字!...

    用户1634449
  • 【数据结构与算法】一起搞定面试中的二叉树题目(二)

    用户1634449
  • Python自动化运维之异常处理

    1、异常 异常就是非正常状态,在Python中使用异常对象来表示异常。若程序在编译或运行过程中发生错误,程序的执行过程就会发生改变,抛出异常对象,程序流进入异常...

    py3study
  • Python的异常概念介绍以及处理

    定义:异常处理就是我们在写Python时,经常看到的报错信息,例如;NameError TypeError ValueError等,这些都是异常。

    砸漏
  • Day15.异常的处理

    例题引导:编写一个计算减法的方法,自己输入两个数,当第一个数小于第二个数时,抛出“被减数不能小于减数"的异常。

    DataScience
  • python异常处理

    东风冷雪
  • Motan中使用异步RPC接口

    这周六参加了一个美团点评的技术沙龙,其中一位老师在介绍他们自研的 RPC 框架时提到一点:RPC 请求分为 sync,future,callback,onewa...

    kirito-moe
  • H5专项测试

    随着Html5的流行,现在很多业务场景使用H5页面来承载,使活动类、运营类的业务功能更便捷在微信、Native端部署,所以H5方面的测试也变得越来越重要。

    用户6367961
  • 原创 | SpringBoot监听rabbitmq和创建交换器,队列

    高级消息队列协议(AMQP)是面向消息的中间件的平台中立的线级协议。Spring AMQP项目将核心Spring概念应用于基于AMQP的消息传递解决方案的开发。...

    润森

扫码关注云+社区

领取腾讯云代金券