二叉树常见面试题小结

这篇文章是二叉树系列的终结篇,总结了一下二叉树常见的手撕面试题,题目多来源于剑指offer,考察的也多数基于对二叉树前中后序遍历的理解,下面具体看题目:

public class TreeNode {
    int val;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode parent = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

1.根据前序和中序遍历序列重建二叉树

    public static TreeNode reRestructure(int[] pre, int pstart, int pend, int[] in, int istart, int iend) {
        if (pend > pend || istart > iend) {
            return null;
        }
        // 根据前序遍历的节点(即根节点)在中序遍历序列中进行查找index
        // 在中序遍历序列中index前的元素是左子树 index后的元素是右子树

        int index = istart;

        while (index <= iend && in[index] != pre[pstart]) {
            index++;
        }

        if (index > iend) {
            // 没有找到 抛异常
            throw new RuntimeException("前序 中序序列参数有误");
        }
        TreeNode root = new TreeNode(pre[pstart]);
        // index节点为根节点 index前 共有index-1-istart+1=index-istart个左节点
        root.left = reRestructure(pre, pstart + 1, pstart + index - istart, in, istart, index - 1);
        root.right = reRestructure(pre, pstart + index - istart + 1, pend, in, index + 1, iend);
        return root;
    }

2.判断b树是不是a树的子树 规定null不是任何树的子树

    public static boolean isSubTree(TreeNode b, TreeNode a) {
        boolean result = false;

        if (b == null || a == null)
            return result;
        if (b.val == a.val) {
            // 进行开始比较
            result = doJudge(b, a);
        }
        if (!result) {
            result = isSubTree(b, a.left);
        }
        if (!result) {
            result = isSubTree(b, a.right);
        }
        return result;
    }

    private static boolean doJudge(TreeNode b, TreeNode a) {
        if (b == null)
            return true;
        if (a == null)
            return false;
        if (b.val != a.val)
            return false;
        return doJudge(b.left, a.left) && doJudge(b.right, a.right);
    }

3.返回一个二叉树的镜像

 public static TreeNode mirror(TreeNode tree) {
        if (tree != null && (tree.left != null || tree.right != null)) {
            TreeNode right = tree.right;
            tree.right = tree.left;
            tree.left = right;

            mirror(tree.left);
            mirror(tree.right);
        }
        return tree;
    }

4.广度遍历二叉树

  public static void breadthFirstSearch(TreeNode root) {
        if (root == null)
            return;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

5.判断一组数据 是否是二叉搜索树的 后序遍历 序列

    // 后序遍历: 左子树->右子树-> 根节点
    public static boolean isPostOrder(int[] array, int start, int end) {
        if (array == null || array.length == 0) // 参数错误
            return false;
        if (start >= end) return true; // 递归终止
        // 后序遍历最后一个节点是根节点
        // 小于根节点的都是左子树 大于根节点的都是右子树 通过这个来判断是否满足后序遍历
        int root = array[end];
        int i = start;
        for (; i < end; i++) {
            if (array[i] > root) {
                break; // 第一个右子树节点
            }
        }
        int index = i;
        for (; i < end; i++) { // 理论上全是右子树节点 要大于根节点
            if (array[i] < root)
                return false;
        }
        // 左子树和右子树 递归继续判断
        return isPostOrder(array, 0, index - 1) && isPostOrder(array, index, end - 1);
    }

    // 上到题的非递归版
    public static boolean isPostOrderNonRecursion(int[] array) {
        if (array == null || array.length == 0)
            return false;
        int len = array.length;
        while (--len > 0) {
            int i = 0;
            while (array[i] < array[len]) i++;
            while (array[i] > array[len]) i++;
            if (i != len)
                return false;
        }
        return true;
    }

6.输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

    // 思路要点 1.判断是不是头节点 2.通过pre节点 和当前stack弹出节点node进行 连接 然后指针移动pre=node
  public static TreeNode converDLinkedNode(TreeNode root) {
        if (root == null)
            return null;
        // 二叉搜索树中序遍历有序
        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        boolean isFirst = true;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode pop = stack.pop();
                if (isFirst) {
                    root = pop;
                    isFirst = false;
                } else {
                    pop.left = pre;
                    pre.right = pop;
                }
                pre = pop;
                node = pop.right;
            }
        }
        return root;
    }

7.计算二叉树的高度

    public static int findDepth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(findDepth(root.left), findDepth(root.right)) + 1;
    }

    // 计算二叉树的高度 // 广度遍历
    public static int findDepthNonRecursion(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        int nextLine = 1;
        int count = 0;
        int level = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            count++;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (count == nextLine) {
                level++;
                nextLine = queue.size();
                count = 0;
            }
        }
        return level;
    }

8.输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径

    // 路径定义为从树的根结点开始往下一直到叶子结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
    ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
        if (root == null) return listAll;
        list.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null)
            listAll.add(new ArrayList<>(list));
        findPath(root.left, target);
        findPath(root.right, target);
        list.remove(list.size() - 1);
        return listAll;
    }

9.输入一棵二叉树，判断该二叉树是否是平衡二叉树。

    // AVL定义:左子树和右子树高度差不超过1
    // 思路: 在求高度时 如果是avl树则返回树的高度 否则返回-1 停止遍历
    public static boolean isBalanced(TreeNode root) {
        return getDepthForAVL(root) == -1;
    }

    private static int getDepthForAVL(TreeNode root) {
        if (root == null)
            return 0;
        int left = getDepthForAVL(root.left);
        if (left == -1)
            return -1;
        int right = getDepthForAVL(root.right);
        if (right == -1)
            return -1;
        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
    }

10.二叉树的序列化 和反序列化

 // 序列化思路: 对于非叶子节点 用node+"," 对于叶子节点 用"#,"表示 前序遍历即可得到序列化string
    public static String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) { // 递归终止条件
            return sb.append("#,").toString();
        }
        sb.append(root.val + ",");
        sb.append(serialize(root.left));
        sb.append(serialize(root.right));
        return sb.toString();
    }

    // 反序列化
    static int index = -1;

    public static TreeNode deSerialize(String str) {
        if (str == null)
            return null;
        index++;
        if (index >= str.length()) return null; // 递归终止条件
        String[] split = str.split(",");
        TreeNode root = null;
        if (!split[index].equals("#")) {
            root = new TreeNode(Integer.valueOf(split[index]));
            root.left = deSerialize(str);
            root.right = deSerialize(str);
        }
        return root;
    }

11.给定一棵二叉搜索树，请找出其中的第k小的结点

    // 思路 二叉搜索树中序遍历有序
    public static TreeNode kthNodeNonRecursion(TreeNode root, int k) {

        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        int count = 0;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode pop = stack.pop();
                count++;
                if (count == k) return pop;
                node = pop.right;
            }
        }
        return null;
    }

    // 递归版
    static int count = 0;
    public static TreeNode kthNode(TreeNode root, int k) {
        if (root == null) return null;
        TreeNode left = kthNode(root.left, k);
        if (left !=null) return left;
        count++;
        if (count == k) return root;
        TreeNode right = kthNode(root.right, k);
        if (right !=null) return right;
        return null;
    }