public boolean isSymmetric(TreeNode root) {
		if (root == null || (root.left == null && root.right == null))
			return true;
		ArrayList<TreeNode> list = new ArrayList<>();
		list.add(root);
		return isFlag(list);
	}

	public boolean isFlag(ArrayList<TreeNode> list) {
		if (list.size() == 0)
			return true;
		ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
		int left = 0, right = list.size() - 1;
		while (left <= right) {
			TreeNode l = list.get(left);
			TreeNode r = list.get(right);
			if (l == null && r == null) {

			} else if (l == null || r == null) {
				return false;
			} else if (l.val != r.val) {
				return false;
			}
			left++;
			right--;
		}
		for (int i = 0; i < list.size(); i++) {
			TreeNode node = list.get(i);
			if (node == null)
				continue;
			else {
				arr.add(node.left);
				arr.add(node.right);
			}
		}
		return isFlag(arr);
	}

class Solution {
    List<List<Integer>>list=new ArrayList<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root==null){
            return list;
        }
        fun(root,0);
        return list;
    }
    public void fun(TreeNode node,int level){
        if(level==list.size()){
            List<Integer>list1=new ArrayList<>();
            list1.add(node.val);
            list.add(list1);
        }else {
            if(level%2==0){
                list.get(level).add(node.val);
            }else {
                list.get(level).add(0,node.val);
            }
        }
        if(node.left!=null){
            fun(node.left,level+1);
        }
        if(node.right!=null){
            fun(node.right,level+1);
        }    
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if(root != null){
            return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
        }
        return 0;
    }
}

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> temp = new LinkedList<>();
        temp.add(root);
        while(temp.size() != 0){
            LinkedList<Integer> list = new LinkedList<>();
            int len = temp.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = temp.poll();
                list.add(node.val);
                if(node.left != null){
                    temp.add(node.left);
                }
                if(node.right != null){
                    temp.add(node.right);
                }
            }
            res.add(0,list);
        }
        return res;
    }
}

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘o开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
            // board[i][j] == '#' 说明已经搜索过了. 
            return;
        }
        board[i][j] = '#';
        dfs(board, i - 1, j); // 上
        dfs(board, i + 1, j); // 下
        dfs(board, i, j - 1); // 左
        dfs(board, i, j + 1); // 右
    }
}

class Solution {
    boolean res = false;

	public boolean hasPathSum(TreeNode root, int targetSum) {
		if (root == null)
			return false;
		int sum = 0;
		dfs(root, sum, targetSum);
		return res;
	}

	public void dfs(TreeNode node, int sum, int target) {
		sum += node.val;
		if (node.left == null && node.right == null) {
			if (sum == target)
				res = true;
		} else if (node.left == null) {
			dfs(node.right, sum, target);
		} else if (node.right == null) {
			dfs(node.left, sum, target);
		} else {
			dfs(node.left, sum, target);
			dfs(node.right, sum, target);
		}
	}
}

class Solution {

    List<Double> res = new ArrayList<>();

    public List<Double> averageOfLevels(TreeNode root) {
		List<TreeNode> arr = new ArrayList<>();
		arr.add(root);
		avg(arr);
		return res;
    }
	
	
	public void avg(List<TreeNode> list) {
		if(list.size() == 0) return;
		double sum = 0;
		List<TreeNode> arr = new ArrayList<>();
		for(int i = 0;i < list.size();i++) {
			TreeNode node = list.get(i);
			sum += node.val;
			if(node.left != null) arr.add(node.left);
			if(node.right != null) arr.add(node.right);
		}
		res.add(sum / list.size());
		avg(arr);
	}
}