【数据结构与算法之面试题】二叉树类面试题

港控/mmm° 2024-03-25 23:01 62阅读 0赞

#### 【数据结构与算法之面试题】二叉树类面试题 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之面试题】二叉树类面试题
         *   *   *  1 完全二叉树的判定
                 *  2 二叉树节点的最大距离
                 *  3 打印二叉树中的重复子树
                 *  4 还原二叉树
                 *  5 二叉树类面试题解题技巧
                 *   *  【1】理解二叉树的定义、性质及相关概念
                     *  【2】利用二叉树遍历解决问题
                     *  【3】利用二叉树的递归特性解决问题

###### 1 完全二叉树的判定 ######

【题目描述】给定一棵二叉树，写一个函数判断它是不是完全二叉树。

其实之前我们也已经学习过了完全二叉树的性质

![在这里插入图片描述][9ab251f564394235aa603f9fdfc96f7c.png_pic_center]

其实不难发现构成一棵完全二叉树的充分必要条件：

*  如果一个完全二叉树的深度(从根节点到底层的叶子节点的层数) 为k，那么在第k - 1层的节点中，当某节点的左孩子为空时，右孩子一定为空。另外在第 k - 1层节点中，如果某节点的左孩子或右孩子为空，则同层节点中的后继节点的左右孩子也一定为空。
    
    ![在这里插入图片描述][3534102fc96d4f96a182c09884b4084f.png_pic_center]
 *  如果一棵完全二叉树的深度为k，那么第1层到第k - 2 层中的全部节点都必须既有左孩子又有右孩子，也就是说第1层到第k - 2层中的全部节点一定构成一棵满二叉树。
    
    ![在这里插入图片描述][55339adec2384cc6a0664ca49a5ecf8b.png_pic_center]

Java 实现代码描述：

import java.util.Arrays;
    import java.util.LinkedList;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: JudgeACompleteBinaryTree
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 14:46
     */
    
    
    class BinaryTreeNode {
        
    
        char data;
        BinaryTreeNode leftChild;
        BinaryTreeNode rightChild;
    
        public BinaryTreeNode(char data) {
        
            this.data = data;
            leftChild = null;
            rightChild = null;
        }
    }
    
    public class JudgeACompleteBinaryTree {
        
    
        private BinaryTreeNode root;
    
        public void CreateBinaryTree(LinkedList<Character> nodeList) {
        
            // 创建二叉树, 将根节点赋值给root
            root = createBinaryTree(nodeList);
        }
    
        private BinaryTreeNode createBinaryTree(LinkedList<Character> nodeList) {
        
            BinaryTreeNode node = null;
            if (nodeList == null || nodeList.isEmpty()) {
        
                return null;
            }
            Character data = nodeList.removeFirst();  // 创建根节点
            if (data != null) {
        
                node = new BinaryTreeNode(data);
                node.leftChild = createBinaryTree(nodeList); // 创建左子树
                node.rightChild = createBinaryTree(nodeList); // 创建右子树
            }
            return node; // 返回根节点
        }
    
        public int getBinaryTreeDepth(BinaryTreeNode root) {
        
            int leftHeight, rightHeight, maxHeight;
            if (root != null) {
        
                leftHeight = getBinaryTreeDepth(root.leftChild);
                rightHeight = getBinaryTreeDepth(root.rightChild);
                maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;
                return maxHeight + 1;
            } else {
        
                return 0;  // 二叉树为null，返回0
            }
        }
    
        // 判断是否是完全二叉树
        public boolean isCompleteBinaryTree() {
        
            int depth = getBinaryTreeDepth(root);
            boolean hasNullChild = false;
    
            if (isCompleteBinaryTree(root, 0, depth - 1, hasNullChild)) {
        
                return true;
            }
            return false;
        }
    
        public boolean isCompleteBinaryTree(BinaryTreeNode node, int curLevel, int depth, boolean hasNullChild) {
        
            if (node == null) {
        
                return true; // 空树也是完全二叉树
            }
            if (curLevel == depth - 1) {
        
                // 当前访问的节点位于二叉树的level - 1层
                if (node.leftChild == null && node.rightChild != null) {
        
                    return false;
                }
                if (!hasNullChild) {
        
                    if (node.leftChild == null || node.rightChild == null) {
        
                        hasNullChild = true;
                    }
                } else {
        
                    if (node.leftChild != null || node.rightChild != null) {
        
                        return false;
                    }
                }
            }
    
            if (curLevel != depth && curLevel != depth - 1) {
        
                if (node.leftChild == null || node.rightChild == null) {
        
                    return false;
                }
            }
            if (!isCompleteBinaryTree(node.leftChild, curLevel + 1, depth, hasNullChild)) {
        
                return false;
            }
            if (!isCompleteBinaryTree(node.rightChild, curLevel + 1, depth, hasNullChild)) {
        
                return false;
            }
            return true;
        }
    
        public static void main(String[] args) {
        
    
            LinkedList<Character> nodes1 = new LinkedList<Character>(Arrays.asList(new Character[]{
        '1', '2', '3', null, null, '5', '6', null, null}));
            LinkedList<Character> nodes2 = new LinkedList<Character>(Arrays.asList(new Character[]{
        '1', null, '2', null, null}));
    
            JudgeACompleteBinaryTree tree1 = new JudgeACompleteBinaryTree();
            JudgeACompleteBinaryTree tree2 = new JudgeACompleteBinaryTree();
    
            tree1.CreateBinaryTree(nodes1);
            tree2.CreateBinaryTree(nodes2);
    
            System.out.println(tree1.isCompleteBinaryTree());
            System.out.println(tree2.isCompleteBinaryTree());
        }
    
    }

运行结果

![在这里插入图片描述][d1ea78a28a584a4ca2ab4c377c58495d.png_pic_center]

###### 2 二叉树节点的最大距离 ######

【题目描述】二叉树节点的距离指两节点之间的边数，例如

![在这里插入图片描述][892491015b0a4005a1af5ada34a49df7.png_pic_center]

这棵树中节点a 和 节点b 之间的距离为3。

编写一个程序，计算一棵二叉树中距离最远的两个节点之间的距离。

思想误区：可能我们会很直观的先想到，二叉树中距离最远的两个节点的最远距离就是根节点的左子树深度和右子树深度的和。像下面这样

![在这里插入图片描述][8a47738cb7b54237ba1926ca91d378bf.png_pic_center]

但是其实这不完全正确，比如下面的情况

![在这里插入图片描述][5ed7ca43b7fa4e06b0ad2a43d91b37bc.png_pic_center]

这种情况用上面那种想法思考就正确了，所以我们在计算这个问题的时候，不仅要考虑根节点的左子树和右子树的深度，还要考虑左子树和右子树中已经得到的最大距离。

Java 算法实现：

import java.util.Arrays;
    import java.util.LinkedList;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MaximumDistanceBetweenBinaryTreeNodes
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 15:35
     */
    
    class BinaryTreeNode {
        
    
        char data;
        BinaryTreeNode leftChild;
        BinaryTreeNode rightChild;
    
        public BinaryTreeNode(char data) {
        
            this.data = data;
            leftChild = null;
            rightChild = null;
        }
    }
    
    public class MaxDistance {
        
        private BinaryTreeNode root;
    
        public void CreateBinaryTree(LinkedList<Character> nodeList) {
        
            // 创建二叉树, 将根节点赋值给root
            root = createBinaryTree(nodeList);
        }
    
        private BinaryTreeNode createBinaryTree(LinkedList<Character> nodeList) {
        
            BinaryTreeNode node = null;
            if (nodeList == null || nodeList.isEmpty()) {
        
                return null;
            }
            Character data = nodeList.removeFirst();  // 创建根节点
            if (data != null) {
        
                node = new BinaryTreeNode(data);
                node.leftChild = createBinaryTree(nodeList); // 创建左子树
                node.rightChild = createBinaryTree(nodeList); // 创建右子树
            }
            return node; // 返回根节点
        }
    
        public int getBinaryTreeDepth(BinaryTreeNode root) {
        
            int leftHeight, rightHeight, maxHeight;
            if (root != null) {
        
                leftHeight = getBinaryTreeDepth(root.leftChild);
                rightHeight = getBinaryTreeDepth(root.rightChild);
                maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;
                return maxHeight + 1;
            } else {
        
                return 0;  // 二叉树为null，返回0
            }
        }
    
        public int getMaxDistance(BinaryTreeNode root) {
        
    
            if (root == null) {
        
                return 0;
            }
    
            int maxLeftDistance = getMaxDistance(root.leftChild);
            int maxRightDistance = getMaxDistance(root.rightChild);
    
            int maxDistance = maxLeftDistance > maxRightDistance ? maxLeftDistance : maxRightDistance;
    
            int leftDepth = getBinaryTreeDepth(root.leftChild);
            int rightDepth = getBinaryTreeDepth(root.rightChild);
    
            int depthSum = leftDepth + rightDepth;
    
            if (depthSum > maxDistance) {
        
                maxDistance = depthSum;
            }
    
            return maxDistance;
    
        }
    
        public static void main(String[] args) {
        
            LinkedList<Character> nodes = new LinkedList<Character>
                    (Arrays.asList(new Character[]{
        '1', '2', '3', '4', '5', null, null, null, null, '6', '7', null, null, '8', null, '9', '0', null, null, null, '1', null, '6', '6', '7', null, null, null, null}));
    
            MaxDistance tree = new MaxDistance();
            tree.CreateBinaryTree(nodes);
            System.out.println(tree.getMaxDistance(tree.root));
        }
    
    }

这棵树的样子

![在这里插入图片描述][94494de46aed4b74ba2692318ca92c51.png_pic_center]

运行结果

![在这里插入图片描述][041f71063a60406cbda0a96e58973284.png_pic_center]

没问题

###### 3 打印二叉树中的重复子树 ######

【题目描述】给定一棵二叉树，找出其中的重复子树，并将重复子树的先序序列打印出来。

举个栗子：

![在这里插入图片描述][a5a85316766740d39615147b2a1d9116.png_pic_center]

这样一棵二叉树，用不同的方框框出这棵二叉树中包含的重复子树。

![在这里插入图片描述][843b6e10b3874e018b1c1a4ff6fc0caa.png_pic_center]

![在这里插入图片描述][96601acc6fb6446996880ca213e2d404.png_pic_center]

![在这里插入图片描述][0baa6b6519104c07924d2c6ba5ea0cc9.png_pic_center]

![在这里插入图片描述][beb076343278415c8f0ce9e515c6e1ce.png_pic_center]

一共这四种情况，最终打印的重复子树的先序序列如下：

2 3 [] [] 4 5 [] [] []
    4 5 [] [] []
    3 [] []
    5 [] []

其实最直观的想法，要想打印一个二叉树的全部重复子树，首先要找到这棵二叉树的全部子树，在此基础上，再判断子树是否重复。

Java 实现描述：

import java.util.Arrays;
    import java.util.HashSet;
    import java.util.LinkedList;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: PrintsDuplicateSubtreesInBinaryTrees
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 16:24
     */
    
    class BinaryTreeNode {
        
        char data;
        BinaryTreeNode leftChild;
        BinaryTreeNode rightChild;
    
        public BinaryTreeNode(char data) {
        
            this.data = data;
            leftChild = null;
            rightChild = null;
        }
    }
    
    public class DuplicateSubtree {
        
    
        private BinaryTreeNode root;
    
        public void CreateBinaryTree(LinkedList<Character> nodeList) {
        
            root = CreateBiTree(nodeList);   //创建二叉树，将根结点赋值给root
        }
    
        public BinaryTreeNode CreateBiTree(LinkedList<Character> nodeList) {
        
            BinaryTreeNode node = null;
            if (nodeList == null || nodeList.isEmpty()) {
        
                return null;
            }
            Character data = nodeList.removeFirst();  //创建根结点
            if (data != null) {
        
                node = new BinaryTreeNode(data);
                node.leftChild = CreateBiTree(nodeList);  //创建左子树
                node.rightChild = CreateBiTree(nodeList); //创建右子树
            }
            return node;
        }
    
        public void printAllDupicateSubTree() {
        
            HashSet<String> set = new HashSet<String>();
            printAllDupicateSubTree(root, set);
        }
    
        public String printAllDupicateSubTree(BinaryTreeNode node, HashSet<String> set) {
        
            if (node.rightChild == null && node.leftChild == null) {
        
                //System.out.println(node.data + "[]" + "[]");
                if (!set.add(node.data + "[]" + "[]")) {
        
                    // 不能加入HashSet，说明该子树有重复
                    System.out.println(node.data + "[]" + "[]");
                }
                return node.data + "[]" + "[]";
            }
            String leftSubtreeSeq = "[]";
            String rightSubtreeSeq = "[]";
            if (node.leftChild != null) {
        
                leftSubtreeSeq = printAllDupicateSubTree(node.leftChild, set);
            }
            if (node.rightChild != null) {
        
                rightSubtreeSeq = printAllDupicateSubTree(node.rightChild, set);
            }
            if (!set.add(node.data + leftSubtreeSeq + rightSubtreeSeq)) {
        
                // 不能加入HashSet，说明该子树有重复
                System.out.println(node.data + leftSubtreeSeq + rightSubtreeSeq);
            }
            return node.data + leftSubtreeSeq + rightSubtreeSeq;
        }
    
        public static void main(String[] args) {
        
            LinkedList<Character> nodes = new LinkedList<Character>(Arrays.asList(new Character[]{
        '1', '2', '3', null, null, '4', '5', null, null, null, '2', '3', null, null, '4', '5', null, null, null}));
    
            DuplicateSubtree tree = new DuplicateSubtree();
            tree.CreateBinaryTree(nodes);
            tree.printAllDupicateSubTree();
        }
    
    
    }

运行结果

![在这里插入图片描述][01b950c352e04b02ad9afcc380856365.png_pic_center]

###### 4 还原二叉树 ######

【题目描述】给定一棵二叉树的先序序列和中序序列，编写一个程序还原该二叉树。

其实根据先序和中序遍历二叉树的特性，不难发现，

*  在二叉树的先序序列中，第1个节点一定是二叉树的根节点，根节点的后面是左子树的先序序列，再后面是右子树的先序序列。
 *  在二叉树的中序序列中，根节点可以将左子树和右子树分开，中序序列左边是左子树的中序，右边是右子树的中序。

所以给定一棵二叉树的先序序列和中序序列，我们可以找到这棵二叉树的根节点，并且可以确定出根节点的左子树和右子树中包含的节点。

其实这就很明显的递归了，因为左右子树也满足这样的特性：

算法描述【适用于每一层递归调用】：

1.  首先通过二叉树的先序序列得到当前子树的根节点。
2.  根据二叉树的遍历特性得到根节点的左子树的先序序列和中序序列，再通过递归调用还原出根节点的左子树。
3.  同理得到根节点的右子树的先序序列和中序序列，再通过递归调用还原出根节点的右子树。
4.  建立根节点与其左右子树的关联，返回根节点。

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: RestoreTheBinaryTree
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 16:52
     */
    
    class BinaryTreeNode {
        
        char data;
        BinaryTreeNode leftChild;
        BinaryTreeNode rightChild;
    
        public BinaryTreeNode(char data) {
        
            this.data = data;
            leftChild = null;
            rightChild = null;
        }
    }
    
    public class RestoreTheBinaryTree {
        
    
        public static BinaryTreeNode createBinaryTree(String preOrderList, String inOrderList) {
        
    
            if (preOrderList == null && inOrderList == null) {
        
                return null;
            }
    
            // 根节点
            char e = preOrderList.charAt(0);
            // 创建根节点
            BinaryTreeNode root = new BinaryTreeNode(e);
    
            String leftInOrderList = null; // 左子树的中序序列
            String leftPreOrderList = null; // 左子树的先序序列
    
            int index = inOrderList.indexOf(e); // 根节点在中序序列中的位置
            // 获取左子树的先序和中序序列
            if (index > 0) {
        
                leftInOrderList = inOrderList.substring(0, index);
                leftPreOrderList = preOrderList.substring(1, index + 1);
            }
    
            String rightInOrderList = null; // 右子树的中序序列
            String rightPreOrderList = null; // 右子树的先序序列
    
            // 获取右子树的先序和中序序列
            if (index + 1 < inOrderList.length()) {
        
                rightInOrderList = inOrderList.substring(index + 1, inOrderList.length());
                rightPreOrderList = preOrderList.substring(index + 1, preOrderList.length());
            }
    
            // 还原左子树和右子树
            root.leftChild = createBinaryTree(leftPreOrderList, leftInOrderList);
            root.rightChild = createBinaryTree(rightPreOrderList, rightInOrderList);
    
            // 返回
            return root;
        }
    
        public static void PostOrderTraverse(BinaryTreeNode root) {
        
            if (root != null) {
        
                PostOrderTraverse(root.leftChild);
                PostOrderTraverse(root.rightChild);
                System.out.print(root.data + " ");
            }
        }
    
        public static void main(String[] args) {
        
    
            String preOrderList = "ABCDE";
            String InOrderList = "ACBDE";
    
            BinaryTreeNode root = createBinaryTree(preOrderList, InOrderList);
    
            // 后序遍历一下二叉树进行验证
            PostOrderTraverse(root);
        }
    
    }

这棵树的样子：

![在这里插入图片描述][80eafee795484e18a75961728a9d38ff.png_pic_center]

运行结果

![在这里插入图片描述][a46da5998e9c415f8a6d36da69be4e38.png_pic_center]

没问题。

###### 5 二叉树类面试题解题技巧 ######

###### 【1】理解二叉树的定义、性质及相关概念 ######

###### 【2】利用二叉树遍历解决问题 ######

###### 【3】利用二叉树的递归特性解决问题 ######

[9ab251f564394235aa603f9fdfc96f7c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a49220164ad242c08e055f3f0fd24211.png
[3534102fc96d4f96a182c09884b4084f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c3407d41626e42409092e5a5173203c7.png
[55339adec2384cc6a0664ca49a5ecf8b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d3844a2de1754aa19f53d24d112cf906.png
[d1ea78a28a584a4ca2ab4c377c58495d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8318e0ba799646bd8499dc94f5ed9853.png
[892491015b0a4005a1af5ada34a49df7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/938cc9ce90cc4556b41888375400a1a8.png
[8a47738cb7b54237ba1926ca91d378bf.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d657578b79314c28ae7ec0c35590fc6c.png
[5ed7ca43b7fa4e06b0ad2a43d91b37bc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1fcd125ad9464c4c93a6b6167ef3e1b3.png
[94494de46aed4b74ba2692318ca92c51.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e886436f5141429a9b8a39d06df2cf98.png
[041f71063a60406cbda0a96e58973284.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7fee21080cd5424e815638d331df9d8c.png
[a5a85316766740d39615147b2a1d9116.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/72409b3e32ea42b2b37a0787d9b18c3e.png
[843b6e10b3874e018b1c1a4ff6fc0caa.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2130757f212f45e283dc31115c6fed89.png
[96601acc6fb6446996880ca213e2d404.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a5e461cb453e41528c5515f1f5e7ef81.png
[0baa6b6519104c07924d2c6ba5ea0cc9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ac1aba1cf4a94027af04e6633a1d26eb.png
[beb076343278415c8f0ce9e515c6e1ce.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/72dec3df3e5f42d6b1329309726ea7c5.png
[01b950c352e04b02ad9afcc380856365.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6b9fdcb5a4fe4f9aa24a69e7d0560a09.png
[80eafee795484e18a75961728a9d38ff.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0fb262b3b23a4f8a95c39e4d452a7011.png
[a46da5998e9c415f8a6d36da69be4e38.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/fb8a5ccef4f5450d99afce7441e486ba.png