java 判断两个二叉树是否完全相同

╰半橙微兮° 2022-07-18 16:27 163阅读 0赞

# java 判断两个二叉树是否完全相同 #

包括了创建二叉树，前序遍历输出（递归），比较二叉树是否相同。

package com.yuxin.learn;
    
    import java.util.LinkedList;
    
    public class Main {
    	private static int[] a1 = { 1, 2, 3, 4, 5, 6 };
    	private static int[] a2 = { 1, 2, 5, 6, 7 };
    	private static int[] a3 = { 1, 2, 5, 6, 7 };
    	private static int[] a4 = { 1, 2, 5, 6, 7, 5, 6 };
    
    	private static class TreeNode {
    		int val;
    		TreeNode left;
    		TreeNode right;
    
    		TreeNode(int val) {
    			this.val = val;
    			this.left = null;
    			this.right = null;
    		}
    	}
    
    	public static TreeNode createTree(int a[]) {
    		int len = a.length;
    		// 将数组的值依次转为Node节点
    		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
    		for (int i = 0; i < len; i++){
    			list.add(new TreeNode(a[i]));
    		}	
    		for (int i = 0; i < len / 2 - 1; i++) {
    			list.get(i).left = list.get(i * 2 + 1);
    			list.get(i).right = list.get(i * 2 + 2);
    		}
    		// 最后一个父节点可能没有右边孩子
    		int last = len / 2 - 1;
    		list.get(last).left = list.get(last * 2 + 1);
    		if (len % 2 == 1) {
    			list.get(last).right = list.get(last * 2 + 2);
    		}
    		return list.get(0);
    	}
    	
    	//递归前序遍历输出二叉树
    	public static void preOder(TreeNode head){
    		System.out.print(head.val+" ");
    		if(head.left!=null) preOder(head.left);
    		if(head.right!=null) preOder(head.right);
    	}
    	
    	//递归判断两个二叉树是否相同
    	public static boolean isSameTree(TreeNode head1, TreeNode head2) {
    		if ((head1 == null && head2 != null) || (head1 != null)
    				&& (head2 == null) || (head1.val != head2.val))
    			return false;
    		if (head1.left == null && head1.right == null && head2.left == null
    				&& head2.right == null && head1.val == head2.val)
    			return true;
    		return isSameTree(head1.left, head2.left)
    				&& isSameTree(head1.right, head2.right);
    	}
    
    	public static void main(String[] args) {
    		
    		TreeNode head1 = createTree(a1);
    		System.out.println("Tree1:");
    		preOder(head1);
    		System.out.println();
    		
    		TreeNode head2 = createTree(a2);
    		System.out.println("Tree2:");
    		preOder(head2);
    		System.out.println();
    		
    		TreeNode head3 = createTree(a3);
    		System.out.println("Tree3:");
    		preOder(head3);
    		System.out.println();
    		
    		TreeNode head4 = createTree(a4);
    		System.out.println("Tree4:");
    		preOder(head4);
    		
    		System.out.println();
    		System.out.println("Tree1和Tree2相同吗？" + isSameTree(head1, head2));
    		System.out.println("Tree2和Tree3相同吗？" + isSameTree(head2, head3));
    		System.out.println("Tree3和Tree4相同吗？" + isSameTree(head3, head4));
    	}
    }