0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

关于二叉树一些数据结构和算法相关的题目

算法与数据结构 2018-02-07 13:57 次阅读

最近总结了一些数据结构和算法相关的题目,这是第一篇文章,关于二叉树的。先上二叉树的数据结构:

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 queue = new LinkedList(); 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&¤t.right!=null){ queue.add(current.left); queue.add(current.right); }else if(current.left!=null&¤t.right==null){ queue.add(current.left); hasNoChild = true; }else if(current.left==null&¤t.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; }

12. 二叉树的前序遍历

迭代解法

ArrayList preOrder(TreeNode root){ Stack stack = new Stack(); ArrayList list = new ArrayList(); if(root == null){ return list; } stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.right!=null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } return list; }

递归解法

ArrayList preOrderReverse(TreeNode root){ ArrayList result = new ArrayList(); preOrder2(root,result); return result; } void preOrder2(TreeNode root,ArrayList result){ if(root == null){ return; } result.add(root.val); preOrder2(root.left,result); preOrder2(root.right,result); }

13. 二叉树的中序遍历

ArrayList inOrder(TreeNode root){ ArrayList list = new ArrayList<(); Stack stack = new Stack(); TreeNode current = root; while(current != null|| !stack.empty()){ while(current != null){ stack.add(current); current = current.left; } current = stack.peek(); stack.pop(); list.add(current.val); current = current.right; } return list; }

14.二叉树的后序遍历

ArrayList postOrder(TreeNode root){ ArrayList list = new ArrayList(); if(root == null){ return list; } list.addAll(postOrder(root.left)); list.addAll(postOrder(root.right)); list.add(root.val); return list; }

15.前序遍历和后序遍历构造二叉树

TreeNode buildTreeNode(int[] preorder,int[] inorder){ if(preorder.length!=inorder.length){ return null; } return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1); } TreeNode myBuildTree(int[] inorder,int instart,int inend,int[] preorder,int prestart,int preend){ if(instart>inend){ return null; } TreeNode root = new TreeNode(preorder[prestart]); int position = findPosition(inorder,instart,inend,preorder[start]); root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart); root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend); return root; } int findPosition(int[] arr,int start,int end,int key){ int i; for(i = start;i<=end;i++){            if(arr[i] == key){                return i;            }        }        return -1;    }

16.在二叉树中插入节点

TreeNode insertNode(TreeNode root,TreeNode node){ if(root == node){ return node; } TreeNode tmp = new TreeNode(); tmp = root; TreeNode last = null; while(tmp!=null){ last = tmp; if(tmp.val>node.val){ tmp = tmp.left; }else{ tmp = tmp.right; } } if(last!=null){ if(last.val>node.val){ last.left = node; }else{ last.right = node; } } return root; }

17.输入一个二叉树和一个整数,打印出二叉树中节点值的和等于输入整数所有的路径

void findPath(TreeNode r,int i){ if(root == null){ return; } Stack stack = new Stack(); int currentSum = 0; findPath(r, i, stack, currentSum); } void findPath(TreeNode r,int i,Stack stack,int currentSum){ currentSum+=r.val; stack.push(r.val); if(r.left==null&&r.right==null){ if(currentSum==i){ for(int path:stack){ System.out.println(path); } } } if(r.left!=null){ findPath(r.left, i, stack, currentSum); } if(r.right!=null){ findPath(r.right, i, stack, currentSum); } stack.pop(); }

18.二叉树的搜索区间

给定两个值 k1 和 k2(k1 < k2)和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。

ArrayList result; ArrayList searchRange(TreeNode root,int k1,int k2){ result = new ArrayList(); searchHelper(root,k1,k2); return result; } void searchHelper(TreeNode root,int k1,int k2){ if(root == null){ return; } if(root.val>k1){ searchHelper(root.left,k1,k2); } if(root.val>=k1&&root.val<=k2){            result.add(root.val);        }        if(root.val

19.二叉树的层次遍历

ArrayList> levelOrder(TreeNode root){ ArrayList> result = new ArrayList>(); if(root == null){ return result; } Queue queue = new LinkedList(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList< level = new ArrayList(): for(int i = 0;i < size ;i++){                TreeNode node = queue.poll();                level.add(node.val);                if(node.left != null){                    queue.offer(node.left);                }                if(node.right != null){                    queue.offer(node.right);                }            }            result.add(Level);        }        return result;    }

20.二叉树内两个节点的最长距离

二叉树中两个节点的最长距离可能有三种情况:1.左子树的最大深度+右子树的最大深度为二叉树的最长距离2.左子树中的最长距离即为二叉树的最长距离3.右子树种的最长距离即为二叉树的最长距离因此,递归求解即可

private static class Result{ int maxDistance; int maxDepth; public Result() { } public Result(int maxDistance, int maxDepth) { this.maxDistance = maxDistance; this.maxDepth = maxDepth; } } int getMaxDistance(TreeNode root){ return getMaxDistanceResult(root).maxDistance; } Result getMaxDistanceResult(TreeNode root){ if(root == null){ Result empty = new Result(0,-1); return empty; } Result lmd = getMaxDistanceResult(root.left); Result rmd = getMaxDistanceResult(root.right); Result result = new Result(); result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1; result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance)); return result; }

21.不同的二叉树

给出 n,问由 1…n 为节点组成的不同的二叉查找树有多少种?

int numTrees(int n ){ int[] counts = new int[n+2]; counts[0] = 1; counts[1] = 1; for(int i = 2;i<=n;i++){            for(int j = 0;j

22.判断二叉树是否是合法的二叉查找树(BST)

一棵BST定义为:节点的左子树中的值要严格小于该节点的值。节点的右子树中的值要严格大于该节点的值。左右子树也必须是二叉查找树。一个节点的树也是二叉查找树。

public int lastVal = Integer.MAX_VALUE; public boolean firstNode = true; public boolean isValidBST(TreeNode root) { // write your code here if(root==null){ return true; } if(!isValidBST(root.left)){ return false; } if(!firstNode&&lastVal >= root.val){ return false; } firstNode = false; lastVal = root.val; if (!isValidBST(root.right)) { return false; } return true; }

深刻的理解这些题的解法思路,在面试中的二叉树题目就应该没有什么问题

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 二叉树
    +关注

    关注

    0

    文章

    74

    浏览量

    12324

原文标题:一篇文章搞定面试中的二叉树

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    计算机二叉树的问题

    各位大神,本人马上要考计算机级了,那个二叉树老是弄不明白,比如题目二叉树共有25个节
    发表于 09-04 09:45

    二叉查找(GIF动图讲解)

    ,则右子树上所有结点的值均大于它的根结点的值;·任意节点的左、右子树也分别为二叉查找;·没有键值相等的节点。二叉查找相比于其他数据结构
    发表于 07-29 15:24

    二叉树算法在单总线威廉希尔官方网站 中的应用

    介绍了单总线威廉希尔官方网站 和二叉树算法。单总线威廉希尔官方网站 可以将地址线、数据线和控制线合成根线,并允许在这根线上挂接多个单总线器件。提出了用二叉树
    发表于 03-16 09:38 20次下载

    二叉树层次遍历算法的验证

    实现二叉树的层次遍历算法,并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。
    发表于 11-28 01:05 2096次阅读
    <b class='flag-5'>二叉树</b>层次遍历<b class='flag-5'>算法</b>的验证

    4中二叉树的遍历方式介绍

    对于一种数据结构而言,遍历是常见操作。二叉树种基本的数据结构,是种每个节点的儿子数目都不多于2的
    的头像 发表于 04-27 17:23 4756次阅读
    4中<b class='flag-5'>二叉树</b>的遍历方式介绍

    二叉树种基础的数据结构类型

    然后我们再定义棵深度也为 3 的二叉树,该二叉树的 n 个结点(n≤7),当从 1 到 n 的每个结点都与上图中的编号结点一一对应时,这二叉树就称为完全
    的头像 发表于 04-13 10:48 4352次阅读
    <b class='flag-5'>二叉树</b>,<b class='flag-5'>一</b>种基础的<b class='flag-5'>数据结构</b>类型

    详解电源二叉树到底是什么

    作为数据结构的基础,分很多种,像 AVL 、红黑二叉搜索....今天我想分享的是
    的头像 发表于 06-06 15:05 1w次阅读
    详解电源<b class='flag-5'>二叉树</b>到底是什么

    二叉树操作的相关知识和代码详解

    数据结构中的重中之重,尤其以各类二叉树为学习的难点。在面试环节中,二叉树也是必考的模块。本文主要讲二叉树操作的
    的头像 发表于 12-12 11:04 2042次阅读
    <b class='flag-5'>二叉树</b>操作的<b class='flag-5'>相关</b>知识和代码详解

    二叉树的前序遍历非递归实现

    通过下面这个动画复习二叉树的前序遍历。 迭代遍历 我们试想下,之前我们借助队列帮我们实现二叉树的层序遍历, 那么可不可以,也借助数据结构
    的头像 发表于 05-28 13:59 1953次阅读

    如何才能够翻转二叉树

    定有所收获! 226.翻转二叉树题目地址:https://leetcode-cn.com/problems/invert-binary-tree/ 翻转二叉树。 这道
    的头像 发表于 09-01 11:45 1745次阅读

    数据结构算法分析中的二叉树与堆有关知识汇总

    该资料包括数据结构算法分析中的二叉树与堆有关的一些知识
    发表于 11-03 09:37 0次下载

    C语言数据结构:什么是二叉树

    完全二叉树:完全二叉树是效率很高的数据结构。对于深度为K,有n个节点的二叉树,当且仅当每个节点都与深度为K的满
    的头像 发表于 04-21 16:20 2509次阅读

    怎么就能构造成二叉树呢?

    直跟着公众号学算法的录友 应该知道,我在二叉树:构造二叉树登场!,已经讲过,只有 中序与后序 和 中序和前序 可以确定颗唯
    的头像 发表于 07-14 11:20 1581次阅读

    使用C语言代码实现平衡二叉树

    这篇博客主要总结平衡二叉树,所以,二叉排序树知识不会提及,但是会用到。
    的头像 发表于 09-21 11:00 1093次阅读

    二叉树的代码实现

    二叉树的主要操作有遍历,例如有先序遍历、中序遍历、后序遍历。在遍历之前,就是创建二叉树,当然,还需要有删除二叉树算法
    的头像 发表于 01-18 10:41 1228次阅读
    <b class='flag-5'>二叉树</b>的代码实现