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

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

作者:IOExceptioner

本文继续一起搞定面试中的二叉树(一)一文总结二叉树相关的面试题。

12. 二叉树的前序遍历

迭代解法

ArrayList<Integer> preOrder(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    ArrayList<Integer> list = new ArrayList<Integer>();
   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<Integer> preOrderReverse(TreeNode root){
   ArrayList<Integer> result = new ArrayList<Integer>();
    preOrder2(root,result);
    return result;
}
void preOrder2(TreeNode root,ArrayList<Integer> result){
    if(root == null){
        return;
    }
    result.add(root.val);
    preOrder2(root.left,result);
    preOrder2(root.right,result);
}

13. 二叉树的中序遍历

ArrayList<Integer> inOrder(TreeNode root){
    ArrayList<Integer> list = new ArrayList<<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    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<Integer> postOrder(TreeNode root){
    ArrayList<Integer> list = new ArrayList<Integer>();
    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<Integer> stack = new Stack<Integer>();
     int currentSum = 0;
     findPath(r, i, stack, currentSum);
}

void findPath(TreeNode r,int i,Stack<Integer> 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<Integer> result;
ArrayList<Integer> searchRange(TreeNode root,int k1,int k2){
    result = new ArrayList<Integer>();
    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<k2){
        searchHelper(root.right,k1,k2);
    }
}

19.二叉树的层次遍历

ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
   ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if(root == null){
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(!queue.isEmpty()){
         int size = queue.size();
         ArrayList<<Integer> level = new ArrayList<Integer>():
         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<i;j++){
            counts[i] += counts[j] * counts[i-j-1];
        }
    }
    return counts[n];
}

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;
}

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

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CAP 理论 —最通俗易懂的解释

    链接:blog.csdn.net/lihao21/article/details/81051631

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

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

    用户1634449
  • Python | 21行轻松搞定拼写检查器

    链接:http://blog.csdn.net/Pwiling/article/details/50573650

    用户1634449
  • LeetCode 222. Count Complete Tree Nodes(二分+位运算)

    题解:DFS 或者BFS都太low,我们可以用O(log(n)^2)的效率解决,n为节点个数,log(n)就是树的高度。

    ShenduCC
  • 面试前准备:二叉树高频面试题和答案

    面试中最常考的说法题主要是:数组、链表、二叉树、Map,深刻的理解上面二叉树算法题的解法思路,在面试中的二叉树题目就应该没有什么问题,祝大家面试顺利。

    五分钟学算法
  • LeetCode:111_Minimum Depth of Binary Tree | 二叉树的最小深度 | Easy

    要求:此题正好和Maximum Depth of Binary Tree一题是相反的,即寻找二叉树的最小的深度值:从根节点到最近的叶子节点的距离。 结题思路:和...

    CloudDeveloper
  • 二叉树实战 22 题,速度收藏吧!

    深刻的理解这些题的解法思路,在面试中的二叉树题目就应该没有什么问题,甚至可以怒他,哈哈。

    Java技术栈
  • 算法篇:树之树的高度

    https://leetcode-cn.com/problems/balanced-binary-tree/

    灰子学技术
  • 剑指Offer-平衡二叉树

    package Tree; /** * 平衡二叉树 * 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 * 平衡二叉树(Balanced Binary ...

    武培轩
  • 算法:递归和分治-理论

    一说起循环,大家都会说一个例子:“从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山...” 这...

    营琪

扫码关注云+社区

领取腾讯云代金券