두 갈래 나무가 다른 두 갈래 나무의 자수인지 검사하다

3559 단어 递归二叉树
검측 방법은 먼저 뿌리 노드를 비교하고 뿌리 노드가 같으면 좌우 나무를 계속 비교하고 귀속하는 방법을 사용한다.루트 노드가 같지 않으면 왼쪽 트리의 루트 노드가 비교할 두 갈래 트리의 루트 노드와 같은지 비교합니다.
package binaryTree;

import java.util.regex.Matcher;

import javax.security.auth.Subject;

/** *   * * @author duola * */

public class hasSubTree {

    public static class BinaryTreeNode {
        BinaryTreeNode left;
        BinaryTreeNode right;
        int val;
    }

    private static boolean issubtree(BinaryTreeNode root1, BinaryTreeNode root2) {
        boolean flag = false;
        if (root2 == null)
            flag = true;
        if (root1 == null)
            flag = false;
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                flag = doeshave(root1, root2);
            }
            if (!flag) {
                flag = issubtree(root1.left, root2);
            }
            if (!flag) {
                flag = issubtree(root1.right, root2);
            }
        }
        return flag;
    }

    private static boolean doeshave(BinaryTreeNode b1, BinaryTreeNode b2) {
        if (b2 == null)
            return true;
        if (b1 == null)
            return false;
        if (b1.val != b2.val)
            return false;
        if (b1.val == b2.val) {
            return doeshave(b1.left, b1.left) && doeshave(b1.right, b2.right);
        }
        return false;
    }

    public static void main(String [] args) {
        BinaryTreeNode root1=new BinaryTreeNode();
        BinaryTreeNode root2=new BinaryTreeNode();
    }




}

좋은 웹페이지 즐겨찾기