浅谈数据结构之树的面试真题（三）

￡神魔★判官ぃ 2023-06-15 11:17 15阅读 0赞

[上一篇][Link 1]

### 浅谈数据结构之树的面试真题（三） ###

*   *  递归和非递归求二叉树最大深度和最小深度
     *  查找两个节点的最近公共祖先
     *  给定一棵树的前序遍历与中序遍历，依据此构造二叉树

## 递归和非递归求二叉树最大深度和最小深度 ##

![在这里插入图片描述][20191123161438133.png]

public class Depth { 
    
        /** * 递归求最大深度 * @param root * @return */
        public int maxDepth(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1;
        }
    
        /** * 非递归求最大深度，利用的是层次遍历的思想 * @param root * @return */
        public int maxDepth2(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            int level = 0;
            while (!queue.isEmpty()) { 
                level++;
                int levelNum = queue.size();
                for (int i = 0; i < levelNum; i++) { 
                    TreeNode node = queue.poll();
                    if (node.left != null) { 
                        queue.offer(node.left);
                    }
                    if (node.right != null) { 
                        queue.offer(node.right);
                    }
                }
            }
            return level;
        }
    
        /** * 递归求最小深度 */
        public int minDepth(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            if (root.left == null && root.right == null) { 
                return 1;
            }
            if (root.left == null && root.right != null) { 
                return minDepth(root.right) + 1;
            }
            if (root.left != null && root.right == null) { 
                return minDepth(root.left) + 1;
            }
            int left = minDepth(root.left);
            int right = minDepth(root.right);
            return Math.min(left, right) + 1;
        }
    
        /** * 非递归求最小深度，利用的是层次遍历的思想 * @param root * @return */
        public int minDepth2(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            int level = 0;
            while (!queue.isEmpty()) { 
                level++;
                int levelNum = queue.size();
                for (int i = 0; i < levelNum; i++) { 
                    TreeNode node = queue.poll();
                    if (node.left == null && node.right == null) { 
                        return level;
                    }
                    if (node.left != null) { 
                        queue.offer(node.left);
                    }
                    if (node.right != null) { 
                        queue.offer(node.right);
                    }
                }
            }
            return 0;
        }
    
        public static void main(String[] args) { 
            TreeNode A = new TreeNode("A");
            TreeNode B = new TreeNode("B");
            TreeNode C = new TreeNode("C");
            TreeNode D = new TreeNode("D");
            TreeNode E = new TreeNode("E");
            TreeNode F = new TreeNode("F");
            TreeNode G = new TreeNode("G");
            TreeNode H = new TreeNode("H");
            TreeNode I = new TreeNode("I");
            TreeNode J = new TreeNode("J");
            TreeNode K = new TreeNode("K");
    
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            D.left = H;
            D.right = I;
            E.right = J;
            C.left = F;
            C.right = G;
            F.right = K;
    
            Depth depth = new Depth();
            System.out.println(depth.maxDepth(A)); // 4
            System.out.println(depth.maxDepth2(A));// 4
            System.out.println(depth.minDepth(A)); // 3
            System.out.println(depth.minDepth2(A));// 3
        }
    }

## 查找两个节点的最近公共祖先 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]

public class LowestAncestor { 
    
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) { 
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) { 
                return root;
            }
            return left != null ? left : right;
        }
    
        public static void main(String[] args) { 
            TreeNode A = new TreeNode("A");
            TreeNode B = new TreeNode("B");
            TreeNode C = new TreeNode("C");
            TreeNode D = new TreeNode("D");
            TreeNode E = new TreeNode("E");
            TreeNode F = new TreeNode("F");
            TreeNode G = new TreeNode("G");
            TreeNode H = new TreeNode("H");
            TreeNode I = new TreeNode("I");
            TreeNode J = new TreeNode("J");
            TreeNode K = new TreeNode("K");
    
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            D.left = H;
            D.right = I;
            E.right = J;
            C.left = F;
            C.right = G;
            F.right = K;
    
            LowestAncestor la = new LowestAncestor();
            TreeNode node = la.lowestCommonAncestor(A, B, F);
            System.out.println(node.value);
        }

## 给定一棵树的前序遍历与中序遍历，依据此构造二叉树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]

public class Interview { 
    
        public TreeNode buildTree(int[] preOrder, int[] inOrder) { 
            if (preOrder == null || inOrder == null) { 
                return null;
            }
            HashMap<Integer, Integer> map = new HashMap();
            for (int i = 0; i < inOrder.length; i++) { 
                map.put(inOrder[i], i);
            }
            return buildTree(preOrder, 0, preOrder.length - 1,
                    inOrder, 0, inOrder.length - 1, map);
        }
    
        private TreeNode buildTree(int [] preOder, int pstart, int pend,
                                   int [] inOrder, int istart, int iend,
                                   HashMap<Integer, Integer> map) { 
            if (pstart > pend || istart > iend) { 
                return null;
            }
    
            TreeNode head = new TreeNode(preOder[pstart] + "");
            int index = map.get(preOder[pstart]);
    
            head.left = buildTree(preOder, pstart + 1, pstart + index - istart,
                    inOrder, istart, index - 1, map);
            head.right = buildTree(preOder, pstart + index - istart + 1, pend,
                    inOrder,index + 1, iend, map);
            return head;
    
        }
    }

[Link 1]: https://blog.csdn.net/cuixhao110/article/details/97371596
[20191123161438133.png]: https://img-blog.csdnimg.cn/20191123161438133.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191123161622996.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191123180422683.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70