자바 는 한 그루 의 나무 가 다른 나무의 서브 구조 인지 아 닌 지 를 판단 합 니 다.

두 그루 의 이 진 트 리 A, B 를 입력 하여 B 가 A 의 서브 구조 인지 아 닌 지 판단 합 니 다.
약속 빈 나 무 는 임의의 나무의 서브 구조 가 아니다.
코드
static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     *  root2    root1    
     *
     * @param root1
     * @param root2
     * @return
     */
    public static boolean hasSub(TreeNode root1, TreeNode root2) {
        boolean result = false;
        //         null,            
        if (root1 != null && root2 != null) {
            // 1.           
            if (root1.val == root2.val) {
                //2.            
                result = isSub(root1, root2);
            }
            //       ,  root1            root2        
            if (!result) {
                result = hasSub(root1.left, root2);
            }
            //       ,root1              ,              root2        
            if (!result) {
                result = hasSub(root1.right, root2);
            }
        }
        return result;
    }

    /**
     *  tree2   tree1    
     * @param tree1
     * @param tree2
     * @return
     */
    public static boolean isSub(TreeNode tree1, TreeNode tree2) {
        //   tree2 null ,       ,  tree2       tree1            ,    
        if (tree2 == null) {
            return true;
        }
        //   tree1   null, tree2  null,        
        //   tree1            , tree2        
        if (tree1 == null) {
            return false;
        }
        //   tree1 tree2            ,  tree2  tree1    
        if (tree1.val != tree2.val) {
            return false;
        }
        //                     
        return isSub(tree1.left, tree2.left) && isSub(tree1.right, tree2.right);
    }

    public static void main(String[] args) {
        TreeNode root1 = buildTree1();
        TreeNode root2 = buildTree2();
        boolean result = hasSub(root1, root2);
        // true
        System.out.println(result);
        root2 = buildTree3();
        result = hasSub(root1, root2);
        // false
        System.out.println(result);
    }

    /**
     *   tree1:
     *          5
     *      3       18
     * @return
     */
    private static TreeNode buildTree1(){
        TreeNode root = new TreeNode(5);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(18);
        root.left = left;
        root.right = right;
        return root;
    }

    /**
     *   tree2:
     *          5
     *      3
     * @return
     */
    private static TreeNode buildTree2(){
        TreeNode root = new TreeNode(5);
        TreeNode left = new TreeNode(3);
        root.left = left;
        return root;
    }

    /**
     *   tree3:
     *          4
     * @return
     */
    private static TreeNode buildTree3(){
        TreeNode root = new TreeNode(4);
        return root;
    }

좋은 웹페이지 즐겨찾기