class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inorder(root,res);
        return res;

    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
        if(root.left != null) {
            inorder(root.left, res);
        }
        res.add(root.val);
        if(root.right != null){
            inorder(root.right,res);
        }
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return inSpread(root,(long)Integer.MIN_VALUE - 1,(long)Integer.MAX_VALUE + 1);
    }
    boolean inSpread(TreeNode node,long left,long right){
        if(node.val <= left || node.val >= right){
            return false;
        }
        if(node.left != null){
            if(!inSpread(node.left, left, node.val)) return false;
        }
        if(node.right != null){
            if(!inSpread(node.right, node.val, right)) return false;
        }
        return true;
    }
}

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 {
    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>> pathSum(TreeNode root, int targetSum) {
       List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        List list = new ArrayList();
        list.add(root.val);
        path(root,root.val,targetSum,res,list);
        return res;
    }
    public void path(TreeNode root, int sum,int target, List<List<Integer>> res,List<Integer> list){
        if(root.left != null){
            list.add(root.left.val);
            sum += root.left.val;
            TreeNode temp = root.left;
            path(temp,sum,target,res,list);
            sum -= list.get(list.size() - 1);
            list.remove(list.size() - 1);
        }
        if(root.right != null){
            list.add(root.right.val);
            sum += root.right.val;
            TreeNode temp = root.right;
            path(temp,sum,target,res,list);
            sum -= list.get(list.size() - 1);
            list.remove(list.size() - 1);
        }
        if(root.left == null && root.right == null && sum == target){
            res.add(new ArrayList<>(list));
        }
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
        res.add(root.val);
        if(root.left != null) {
            inorder(root.left, res);
        }
        if(root.right != null){
            inorder(root.right,res);
        }
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
        if(root.left != null) {
            inorder(root.left, res);
        }
        if(root.right != null){
            inorder(root.right,res);
        }
        res.add(root.val);
    }
}

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 {
    public int numIslands(char[][] grid) {
        int res = 0;
        for(int row = 0;row < grid.length;row++) {
        	for(int col = 0;col < grid[0].length;col++) {
        		if(grid[row][col] == '1') {
        			res++;
        			find(grid,row,col);
        		}else {
        			continue;
        		}
        	}
        }
        return res;
    }

	public void find(char[][] grid, int row, int col) {
		if(row >= 0 && col >= 0 && row < grid.length && col < grid[0].length && grid[row][col] == '1') {
			grid[row][col] = '2';
			// 上下左右
			find(grid,row - 1,col);
			find(grid,row + 1,col);
			find(grid,row,col - 1);
			find(grid,row,col + 1);
		}
		return;
	}
}

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);
		}
	}
}