几道和「二叉树」有关的算法面试题

二叉树的详细讲解请戳这:懵逼树上懵逼果:学习二分搜索树

1. 二叉树的前序遍历

题目来源于 LeetCode 第 144 号问题:二叉树的前序遍历。

题目描述

给定一个二叉树,返回它的 前序 遍历。

题目解析

栈(Stack)的思路来处理问题。

前序遍历的顺序为根-左-右,具体算法为:

  • 把根节点push到栈中

  • 循环检测栈是否为空,若不空,则取出栈顶元素,保存其值

  • 看其右子节点是否存在,若存在则push到栈中

  • 看其左子节点,若存在,则push到栈中。

动画描述

几道和「二叉树」有关的算法面试题
二叉树的前序遍历

代码实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        //第一步是将根节点压入栈中
        stack.push(root);
        //当栈不为空时,出栈的元素插入list尾部。
        while(!stack.isEmpty()){
            root = stack.pop();
            list.add(root.val);
            if(root.right != null) stack.push(root.right);
            if(root.left != null) stack.push(root.left);
        }
        return list;
    }
}

2. 二叉树的中序遍历

题目来源于 LeetCode 第 94 号问题:二叉树的中序遍历。

题目描述

给定一个二叉树,返回它的 中序 遍历。

题目解析

栈(Stack)的思路来处理问题。

中序遍历的顺序为左-根-右,具体算法为:

  • 从根节点开始,先将根节点压入栈

  • 然后再将其所有左子结点压入栈,取出栈顶节点,保存节点值

  • 再将当前指针移到其右子节点上,若存在右子节点,则在下次循环时又可将其所有左子结点压入栈中

动画描述

几道和「二叉树」有关的算法面试题
二叉树的中序遍历

代码实现

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    list.add(cur.val);
                    cur = cur.right;
                }
            }
            return list;
        }
}

3. 二叉树的后序遍历

题目来源于 LeetCode 第 145 号问题:二叉树的后序遍历。

题目描述

给定一个二叉树,返回它的 后序 遍历。

题目解析

栈(Stack)的思路来处理问题。

后序遍历的顺序为左-右-根,具体算法为:

  • 先将根结点压入栈,然后定义一个辅助结点head

  • while循环的条件是栈不为空

  • 在循环中,首先将栈顶结点t取出来

  • 如果栈顶结点没有左右子结点,或者其左子结点是head,或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中,并将栈顶元素移出栈,然后将head指向栈顶元素

  • 否则的话就看如果右子结点不为空,将其加入栈

  • 再看左子结点不为空的话,就加入栈

动画描述

几道和「二叉树」有关的算法面试题
二叉树的后序遍历

代码实现

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while(!stack.isEmpty()){
        TreeNode node = stack.pop();
        if(node.left != null) stack.push(node.left);//和传统先序遍历不一样,先将左结点入栈
        if(node.right != null) stack.push(node.right);//后将右结点入栈
        res.add(0,node.val);                        //逆序添加结点值
    }     
    return res;
   }
}

4. 二叉树的层序遍历

题目来源于 LeetCode 第 102 号问题:二叉树的层序遍历。

题目描述

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / 
  9  20
    /  
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

题目解析

该问题需要用到队列

  • 建立一个queue

  • 先把根节点放进去,这时候找根节点的左右两个子节点

  • 去掉根节点,此时queue里的元素就是下一层的所有节点

  • 用for循环遍历,将结果存到一个一维向量里

  • 遍历完之后再把这个一维向量存到二维向量里

  • 以此类推,可以完成层序遍历

动画描述

几道和「二叉树」有关的算法面试题
二叉树的层序遍历

代码实现

public List<List<Integer>> levelOrder(TreeNode root) {
    if(root == null)
        return new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while(!queue.isEmpty()){
        int count = queue.size();
        List<Integer> list = new ArrayList<Integer>();
        while(count > 0){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
            count--;
        }
        res.add(list);
    }
    return res;
}

5. 平衡二叉树

题目来源于 LeetCode 第 110 号问题:平衡二叉树。

题目描述

给定一个二叉树,判断它是否是高度平衡的二叉树。

题目解析

采取后序遍历的方式遍历二叉树的每一个结点。

在遍历到一个结点之前已经遍历了它的左右子树,那么只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶结点的路径的长度),就可以一边遍历一边判断每个结点是不是平衡的。

代码实现

class Solution {
    private boolean isBalanced = true;
    public boolean isBalanced(TreeNode root) {
        getDepth(root);
        return isBalanced;
    }
      public int getDepth(TreeNode root) {
      if (root == null)
            return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if (Math.abs(left - right) > 1) {
            isBalanced = false;
        }
        return right > left ? right + 1 : left + 1;
      }
}

6. 对称二叉树

题目来源于 LeetCode 第 101 号问题:对称二叉树。

题目描述

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / 
  2   2
 /  / 
3  4 4  3

题目解析

用递归做比较简单:一棵树是对称的等价于它的左子树和右子树两棵树是对称的,问题就转变为判断两棵树是否对称。

代码实现

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == nullreturn true;
        //把问题变成判断两棵树是否是对称的
        return isSym(root.left, root.right);
    }
    //判断的是根节点为r1和r2的两棵树是否是对称的
    public boolean isSym(TreeNode r1, TreeNode r2){
        if(r1 == null && r2 == nullreturn true;
        if(r1 == null || r2 == nullreturn false;
        //这两棵树是对称需要满足的条件:
        //1.俩根节点相等。 2.树1的左子树和树2的右子树,树2的左子树和树1的右子树都得是对称的
        return r1.val == r2.val && isSym(r1.left, r2.right) 
                            && isSym(r1.right, r2.left);
    }
}

7. 重建二叉树

题目来源于 剑指 offer :重建二叉树。

题目描述

根据二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

preorder = [3,9,20,15,7]
inorder =  [9,3,15,20,7]

题目解析

前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分成两部分,左部分为树的左子树中序遍历结果,右部分为树的右子树中序遍历的结果。

动画描述

几道和「二叉树」有关的算法面试题
动画来源于 CS-Notes

代码实现

// 缓存中序遍历数组每个值对应的索引
private Map<Integer, Integer> indexForInOrders = new HashMap<>();

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    for (int i = 0; i < in.length; i++)
        indexForInOrders.put(in[i], i);
    return reConstructBinaryTree(pre, 0, pre.length - 10);
}

private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
    if (preL > preR)
        return null;
    TreeNode root = new TreeNode(pre[preL]);
    int inIndex = indexForInOrders.get(root.val);
    int leftTreeSize = inIndex - inL;
    root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
    root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
    return root;
}




推荐阅读:

几道和「堆栈、队列」有关的面试算法题

几道和「哈希表」有关的面试算法题

   链表算法面试问题?看我就够了!

  

几道和「二叉树」有关的算法面试题

欢迎关注这个会做动画的程序员?

  

喜欢就点击“好看”吧!