面试准备（十六）二叉树深度优先广度优先

雨点打透心脏的1/2处 2022-10-13 05:13 150阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70][]

深度优先：递归，从子节点往上计算深度，计算到根节点取最小值

广度优先：从根节点往下找，找到叶子结点为止

**代码：**

import java.util.LinkedList;
    import java.util.Queue;
    
    public class TreeDeep {
    
        static class TreeNode{
            int val;
            TreeNode left;
            TreeNode right;
            int deep;
    
            public TreeNode(int val, TreeNode left, TreeNode right) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
    
        public static void main(String[] args) {
            TreeNode node7 = new TreeNode(7, null, null);
            TreeNode node6 = new TreeNode(6, node7, null);
            TreeNode node5 = new TreeNode(5, null, null);
            TreeNode node4 = new TreeNode(4, null, null);
            TreeNode node3 = new TreeNode(3, node6, null);
            TreeNode node2 = new TreeNode(2, node4, node5);
            TreeNode node1 = new TreeNode(1, node2, node3);
    
            System.out.println(minDepath(node1));
        }
    
        //递归 深度优先
        public static int minDepath(TreeNode root){
            if (root==null){
                return 0;
            }
            if(root.left==null && root.right==null){
                return 1;
            }
            int min = Integer.MAX_VALUE;
            if(root.left!=null){
                min = Math.min(minDepath(root.left),min);
            }
            if(root.right!=null){
                min=Math.min(minDepath(root.right),min);
            }
            return min+1;
        }
    
        //广度优先
        public static int minDepath2(TreeNode root){
            if (root==null) {
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList();
            root.deep=1;
            //放入 root
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode treeNode = queue.poll();
                if(treeNode.left==null && treeNode.right==null){
                    return treeNode.deep;
                }
                if(treeNode.left!=null){
                    treeNode.left.deep=treeNode.deep+1;
                    queue.offer(treeNode.left);
                }
                if(treeNode.right!=null){
                    treeNode.right.deep=treeNode.deep+1;
                    queue.offer(treeNode.right);
                }
            }
            return 0;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70]: /images/20221005/a8ba840823994e6ca2a42c5dfc1bcec7.png