手册   游戏   WEB   字典   单词   在线工具  

一篇文章搞定面试中的二叉树题目 (java 实现)

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

先上二叉树的数据结构:

  1. class TreeNode{
  2.     int val;
  3.     // 左孩子
  4.     TreeNode left;
  5.     // 右孩子
  6.     TreeNode right;
  7. }

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

1. 求二叉树的最大深度

  1. int maxDeath(TreeNode node){
  2.     if(node==null){
  3.         return 0;
  4.     }
  5.     int left = maxDeath(node.left);
  6.     int right = maxDeath(node.right);
  7.     return Math.max(left,right) + 1;
  8. }

2. 求二叉树的最小深度

  1. int getMinDepth(TreeNode root){
  2.         if(root == null){
  3.             return 0;
  4.         }
  5.         return getMin(root);
  6.     }
  7.     int getMin(TreeNode root){
  8.         if(root == null){
  9.             return Integer.MAX_VALUE;
  10.         }
  11.         if(root.left == null&&root.right == null){
  12.             return 1;
  13.         }
  14.         return Math.min(getMin(root.left),getMin(root.right)) + 1;
  15.     }

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

  1. int numOfTreeNode(TreeNode root){
  2.         if(root == null){
  3.             return 0;
  4.         }
  5.         int left = numOfTreeNode(root.left);
  6.         int right = numOfTreeNode(root.right);
  7.         return left + right + 1;
  8.     }

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

  1. int numsOfNoChildNode(TreeNode root){
  2.         if(root == null){
  3.             return 0;
  4.         }
  5.         if(root.left==null&&root.right==null){
  6.             return 1;
  7.         }
  8.         return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
  9.     }

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

  1. int numsOfkLevelTreeNode(TreeNode root,int k){
  2.             if(root == null||k<1){
  3.                 return 0;
  4.             }
  5.             if(k==1){
  6.                 return 1;
  7.             }
  8.             int numsLeft = numsOfkLevelTreeNode(root.left,k-1);
  9.             int numsRight = numsOfkLevelTreeNode(root.right,k-1);
  10.             return numsLeft + numsRight;
  11.         }

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

  1. boolean isBalanced(TreeNode node){
  2.         return maxDeath2(node)!=-1;
  3.     }
  4.     int maxDeath2(TreeNode node){
  5.         if(node == null){
  6.             return 0;
  7.         }
  8.         int left = maxDeath2(node.left);
  9.         int right = maxDeath2(node.right);
  10.         if(left==-1||right==-1||Math.abs(left-right)>1){
  11.             return -1;
  12.         }
  13.         return Math.max(left, right) + 1;
  14.     }

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

什么是完全二叉树呢?

完全二叉树_百度百科

  1. boolean isCompleteTreeNode(TreeNode root){
  2.         if(root == null){
  3.             return false;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  6.         queue.add(root);
  7.         boolean result = true;
  8.         boolean hasNoChild = false;
  9.         while(!queue.isEmpty()){
  10.             TreeNode current = queue.remove();
  11.             if(hasNoChild){
  12.                 if(current.left!=null||current.right!=null){
  13.                     result = false;
  14.                     break;
  15.                 }
  16.             }else{
  17.                 if(current.left!=null&¤t.right!=null){
  18.                     queue.add(current.left);
  19.                     queue.add(current.right);
  20.                 }else if(current.left!=null&¤t.right==null){
  21.                     queue.add(current.left);
  22.                     hasNoChild = true;
  23.                 }else if(current.left==null&¤t.right!=null){
  24.                     result = false;
  25.                     break;
  26.                 }else{
  27.                     hasNoChild = true;
  28.                 }
  29.             }
  30.         }
  31.         return result;
  32.     }

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

  1. boolean isSameTreeNode(TreeNode t1,TreeNode t2){
  2.         if(t1==null&&t2==null){
  3.             return true;
  4.         }
  5.         else if(t1==null||t2==null){
  6.             return false;
  7.         }
  8.         if(t1.val != t2.val){
  9.             return false;
  10.         }
  11.         boolean left = isSameTreeNode(t1.left,t2.left);
  12.         boolean right = isSameTreeNode(t1.right,t2.right);
  13.         return left&&right;
  14.     }

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

  1. boolean isMirror(TreeNode t1,TreeNode t2){
  2.         if(t1==null&&t2==null){
  3.             return true;
  4.         }
  5.         if(t1==null||t2==null){
  6.             return false;
  7.         }
  8.         if(t1.val != t2.val){
  9.             return false;
  10.         }
  11.         return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
  12.     }

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

  1. TreeNode mirrorTreeNode(TreeNode root){
  2.         if(root == null){
  3.             return null;
  4.         }
  5.         TreeNode left = mirrorTreeNode(root.left);
  6.         TreeNode right = mirrorTreeNode(root.right);
  7.         root.left = right;
  8.         root.right = left;
  9.         return root;
  10.     }

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

  1. TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){
  2.         if(findNode(root.left,t1)){
  3.             if(findNode(root.right,t2)){
  4.                 return root;
  5.             }else{
  6.                 return getLastCommonParent(root.left,t1,t2);
  7.             }
  8.         }else{
  9.             if(findNode(root.left,t2)){
  10.                 return root;
  11.             }else{
  12.                 return getLastCommonParent(root.right,t1,t2)
  13.             }
  14.         }
  15.     }
  16.     // 查找节点 node 是否在当前 二叉树中
  17.     boolean findNode(TreeNode root,TreeNode node){
  18.         if(root == null || node == null){
  19.             return false;
  20.         }
  21.         if(root == node){
  22.             return true;
  23.         }
  24.         boolean found = findNode(root.left,node);
  25.         if(!found){
  26.             found = findNode(root.right,node);
  27.         }
  28.         return found;
  29.     }

12. 二叉树的前序遍历

迭代解法

  1. ArrayList<Integer> preOrder(TreeNode root){
  2.         Stack<TreeNode> stack = new Stack<TreeNode>();
  3.         ArrayList<Integer> list = new ArrayList<Integer>();
  4.         if(root == null){
  5.             return list;
  6.         }
  7.         stack.push(root);
  8.         while(!stack.empty()){
  9.             TreeNode node = stack.pop();
  10.             list.add(node.val);
  11.             if(node.right!=null){
  12.                 stack.push(node.right);
  13.             }
  14.             if(node.left != null){
  15.                 stack.push(node.left);
  16.             }
  17.         }
  18.         return list;
  19.     }

递归解法

  1. ArrayList<Integer> preOrderReverse(TreeNode root){
  2.         ArrayList<Integer> result = new ArrayList<Integer>();
  3.         preOrder2(root,result);
  4.         return result;
  5.     }
  6.     void preOrder2(TreeNode root,ArrayList<Integer> result){
  7.         if(root == null){
  8.             return;
  9.         }
  10.         result.add(root.val);
  11.         preOrder2(root.left,result);
  12.         preOrder2(root.right,result);
  13.     }

13. 二叉树的中序遍历

  1. ArrayList<Integer> inOrder(TreeNode root){
  2.         ArrayList<Integer> list = new ArrayList<<Integer>();
  3.         Stack<TreeNode> stack = new Stack<TreeNode>();
  4.         TreeNode current = root;
  5.         while(current != null|| !stack.empty()){
  6.             while(current != null){
  7.                 stack.add(current);
  8.                 current = current.left;
  9.             }
  10.             current = stack.peek();
  11.             stack.pop();
  12.             list.add(current.val);
  13.             current = current.right;
  14.         }
  15.         return list;
  16.     }

14. 二叉树的后序遍历

  1. ArrayList<Integer> postOrder(TreeNode root){
  2.         ArrayList<Integer> list = new ArrayList<Integer>();
  3.         if(root == null){
  4.             return list;
  5.         }
  6.         list.addAll(postOrder(root.left));
  7.         list.addAll(postOrder(root.right));
  8.         list.add(root.val);
  9.         return list;
  10.     }

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

  1. TreeNode buildTreeNode(int[] preorder,int[] inorder){
  2.         if(preorder.length!=inorder.length){
  3.             return null;
  4.         }
  5.         return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1);
  6.     }
  7.     TreeNode myBuildTree(int[] inorder,int instart,int inend,int[] preorder,int prestart,int preend){
  8.         if(instart>inend){
  9.             return null;
  10.         }
  11.         TreeNode root = new TreeNode(preorder[prestart]);
  12.         int position = findPosition(inorder,instart,inend,preorder[start]);
  13.         root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart);
  14.         root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend);
  15.         return root;
  16.     }
  17.     int findPosition(int[] arr,int start,int end,int key){
  18.         int i;
  19.         for(i = start;i<=end;i++){
  20.             if(arr[i] == key){
  21.                 return i;
  22.             }
  23.         }
  24.         return -1;
  25.     }

16. 在二叉树中插入节点

  1. TreeNode insertNode(TreeNode root,TreeNode node){
  2.         if(root == node){
  3.             return node;
  4.         }
  5.         TreeNode tmp = new TreeNode();
  6.         tmp = root;
  7.         TreeNode last = null;
  8.         while(tmp!=null){
  9.             last = tmp;
  10.             if(tmp.val>node.val){
  11.                 tmp = tmp.left;
  12.             }else{
  13.                 tmp = tmp.right;
  14.             }
  15.         }
  16.         if(last!=null){
  17.             if(last.val>node.val){
  18.                 last.left = node;
  19.             }else{
  20.                 last.right = node;
  21.             }
  22.         }
  23.         return root;
  24.     }

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

  1. void findPath(TreeNode r,int i){
  2.         if(root == null){
  3.             return;
  4.         }
  5.         Stack<Integer> stack = new Stack<Integer>();
  6.         int currentSum = 0;
  7.         findPath(r, i, stack, currentSum);
  8.     }
  9.     void findPath(TreeNode r,int i,Stack<Integer> stack,int currentSum){
  10.         currentSum+=r.val;
  11.         stack.push(r.val);
  12.         if(r.left==null&&r.right==null){
  13.             if(currentSum==i){
  14.                 for(int path:stack){
  15.                     System.out.println(path);
  16.                 }
  17.             }
  18.         }
  19.         if(r.left!=null){
  20.             findPath(r.left, i, stack, currentSum);
  21.         }
  22.         if(r.right!=null){
  23.             findPath(r.right, i, stack, currentSum);
  24.         }
  25.         stack.pop();
  26.     }

18. 二叉树的搜索区间

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

  1. ArrayList<Integer> result;
  2.     ArrayList<Integer> searchRange(TreeNode root,int k1,int k2){
  3.         result = new ArrayList<Integer>();
  4.         searchHelper(root,k1,k2);
  5.         return result;
  6.     }
  7.     void searchHelper(TreeNode root,int k1,int k2){
  8.         if(root == null){
  9.             return;
  10.         }
  11.         if(root.val>k1){
  12.             searchHelper(root.left,k1,k2);
  13.         }
  14.         if(root.val>=k1&&root.val<=k2){
  15.             result.add(root.val);
  16.         }
  17.         if(root.val<k2){
  18.             searchHelper(root.right,k1,k2);
  19.         }
  20.     }

19. 二叉树的层次遍历

  1. ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
  2.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  3.         if(root == null){
  4.             return result;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  7.         queue.offer(root);
  8.         while(!queue.isEmpty()){
  9.             int size = queue.size();
  10.             ArrayList<<Integer> level = new ArrayList<Integer>():
  11.             for(int i = 0;i <size ;i++){
  12.                 TreeNode node = queue.poll();
  13.                 level.add(node.val);
  14.                 if(node.left != null){
  15.                     queue.offer(node.left);
  16.                 }
  17.                 if(node.right != null){
  18.                     queue.offer(node.right);
  19.                 }
  20.             }
  21.             result.add(Level);
  22.         }
  23.         return result;
  24.     }

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

二叉树中两个节点的最长距离可能有三种情况:

1. 左子树的最大深度 + 右子树的最大深度为二叉树的最长距离

2. 左子树中的最长距离即为二叉树的最长距离

3. 右子树种的最长距离即为二叉树的最长距离

因此, 递归求解即可

  1. private static class Result{
  2.     int maxDistance;
  3.     int maxDepth;
  4.     public Result() {
  5.     }
  6.     public Result(int maxDistance, int maxDepth) {
  7.         this.maxDistance = maxDistance;
  8.         this.maxDepth = maxDepth;
  9.     }
  10. }
  11.     int getMaxDistance(TreeNode root){
  12.       return getMaxDistanceResult(root).maxDistance;
  13.     }
  14.     Result getMaxDistanceResult(TreeNode root){
  15.         if(root == null){
  16.             Result empty = new Result(0,-1);
  17.             return empty;
  18.         }
  19.         Result lmd = getMaxDistanceResult(root.left);
  20.         Result rmd = getMaxDistanceResult(root.right);
  21.         Result result = new Result();
  22.         result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1;
  23.         result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance));
  24.         return result;
  25.     }

21. 不同的二叉树

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

  1. int numTrees(int n ){
  2.         int[] counts = new int[n+2];
  3.         counts[0] = 1;
  4.         counts[1] = 1;
  5.         for(int i = 2;i<=n;i++){
  6.             for(int j = 0;j<i;j++){
  7.                 counts[i] += counts[j] * counts[i-j-1];
  8.             }
  9.         }
  10.         return counts[n];
  11.     }

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

一棵 BST 定义为:

节点的左子树中的值要严格小于该节点的值.

节点的右子树中的值要严格大于该节点的值.

左右子树也必须是二叉查找树.

一个节点的树也是二叉查找树.

  1. public int lastVal = Integer.MAX_VALUE;
  2.     public boolean firstNode = true;
  3.     public boolean isValidBST(TreeNode root) {
  4.         // write your code here
  5.         if(root==null){
  6.             return true;
  7.         }
  8.         if(!isValidBST(root.left)){
  9.             return false;
  10.         }
  11.         if(!firstNode&&lastVal>= root.val){
  12.             return false;
  13.         }
  14.         firstNode = false;
  15.         lastVal = root.val;
  16.         if (!isValidBST(root.right)) {
  17.             return false;
  18.         }
  19.         return true;
  20.     }

来源: http://www.bubuko.com/infodetail-3037460.html


与本文相关文章

  1. 图解汉诺塔问题 ( Java 递归实现)
  2. LeetCode 算法题 - Add Strings(Java 实现)
  3. Trie 树的 java 实现
  4. Java 创建二叉树, 二叉树的遍历
  5. LeetCode 算法题 - Heaters(Java 实现)
  6. 基于 C-W 节约算法的车辆路径规划问题的 Java 实现
  7. Java 使用递归实现全排列的代码
  8. 手把手教你使用 Java 实现一个神经网络
暂无,快来抢沙发吧！
更多





黑ICP备17005318号-1