描述

101. 对称二叉树 - 力扣（Leetcode）

分析

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.util.Deque;
import java.util.Queue;
import java.util.LinkedList;

//101. 对称二叉树
public class SymmetricTree101 {
	public static void main(String[] args){

		TreeNode root = buildTree(new int[]{1,2,2,3,4,4,3});
		if (new Solution().isSymmetric(root)) {
			System.out.println("这是个对称二叉树");
		}
	}
	/**
	 *二叉树的构建
	 * int[] -> 二叉树
	 */
	 public static TreeNode buildTree(int[] arr) {
        return buildTreeHelper(arr, 0);
    }

    public static TreeNode buildTreeHelper(int[] arr, int index) {
        if (index >= arr.length) {
            return null;
        }

        TreeNode node = new TreeNode(arr[index]);

        node.left = buildTreeHelper(arr, 2 * index + 1);
        node.right = buildTreeHelper(arr, 2 * index + 2);

        return node;
    }


}

class Solution {
	//递归解决
    public boolean isSymmetric(TreeNode root) {
    	return compare(root.left, root.right);
    }
    private boolean compare(TreeNode left, TreeNode right){
    	//含null的情况
    	if (left == null && right == null) {
    		return true;
    	}
    	if (left != null && right == null) {
    		return false;
    	}
    	if (left == null && right != null) {
    		return false;
    	}
    	//不含null的情况
    	if (left.val != right.val) {
    		return false;
    	}
    	boolean bOuter = compare(left.left, right.right);
    	boolean bInner = compare(left.right, right.left);
    	return bOuter && bInner;
    }

    //双向队列解决 offer poll
    public boolean isSymmetric2(TreeNode root) {
    	Deque<TreeNode> deque = new LinkedList<>();
    	deque.offerFirst(root.left);
    	deque.offerLast(root.right);
    	TreeNode leftNode;
    	TreeNode rightNode;

    	while(!deque.isEmpty()){
    		leftNode = deque.pollFirst();
    		rightNode = deque.pollLast();
    		if (leftNode == null && rightNode ==  null) {
    			continue;
    		}
    		if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
    			return false;
    		}
    		deque.offerFirst(leftNode.left);//左外
    		deque.offerFirst(leftNode.right);//左内
    		deque.offerLast(rightNode.right);//右外
    		deque.offerLast(rightNode.left);//右内
    	}
    	return true;
    }
    //单向队列解决
    public boolean isSymmetric3(TreeNode root) {
    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.offer(root.left);
    	queue.offer(root.right);
    	TreeNode leftNode;
    	TreeNode rightNode;

    	while(!queue.isEmpty()){
    		leftNode = queue.poll();
    		rightNode = queue.poll();
    		if (leftNode == null && rightNode ==  null) {
    			continue;
    		}
    		if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
    			return false;
    		}
    		queue.offer(leftNode.left);//左外
    		queue.offer(rightNode.right);//右外
    		queue.offer(leftNode.right);//左内
    		queue.offer(rightNode.left);//右内
    	}
    	return true;
    }
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

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

总结