1.Note
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;
}
}
- 平衡二叉树：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
- 搜索二叉树：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
- 完全二叉树：
叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
- 深度优先搜索
depth first search
dfs
- 广度优先搜索
breadth first search
bfs
2. LeetCode题目
package leetcode;
import java.util.*;
public class TreeDemo {
public static void main(String[] args) {
System.out.println(Long.MAX_VALUE);
System.out.println(Long.MIN_VALUE);
System.out.println(Integer.MAX_VALUE);
System.out.println(Integer.MIN_VALUE);
}
}
/**
* 538. 把二叉搜索树转换为累加树
*/
class Solution39 {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
dfsPostorder(root);
return root;
}
public void dfsPostorder(TreeNode root) {
if (root == null) return;
dfsPostorder(root.right);
sum += root.val;
root.val = sum;
dfsPostorder(root.left);
}
}
/**
* 108. 将有序数组转换为二叉搜索树
*/
// 二分法，平均分，高度差不可能大于1，我竟然能瞎写出来，瞎蒙
class Solution38 {
public TreeNode sortedArrayToBST(int[] nums) {
TreeNode root = dfsBuild(nums, 0, nums.length - 1);
return root;
}
public TreeNode dfsBuild(int[] nums, int l, int r) {
if (l > r) return null;
int curIndex = (l - r) / 2 + r;
TreeNode node = new TreeNode(nums[curIndex]);
node.left = dfsBuild(nums, l, curIndex - 1);
node.right = dfsBuild(nums, curIndex + 1, r);
return node;
}
}
/**
* @date 2021 10 27
* 450. 删除二叉搜索树中的节点
*/
class Solution37 {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
return root.right;
}
}
return root;
}
}
/**
* 701.二叉搜索树中的插入操作
*/
class Solution36 {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
TreeNode node = root;
while (node != null) {
if (node.val > val) {
if (node.left == null) {
node.left = new TreeNode(val);
break;
} else {
node = node.left;
}
} else {
if (node.right == null) {
node.right = new TreeNode(val);
break;
} else {
node = node.right;
}
}
}
return root;
}
}
class Solution35 {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
/**
* @date 2021 10 26
* 235. 二叉搜索树的最近公共祖先
*/
class Solution34 {
// 左右子树的公共祖先是唯一的
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (true) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
return root;
}
}
}
}
/**
* 236. 二叉树的最近公共祖先
*/
class Solution33 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 找到p、q节点或者为null时，返回root
if (root == null || root == p || root == q) return root;
// 找左子树是否包含p、q，如果有则left == q或者p；
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 同上
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) { //找到公共祖先节点
return root;
// 返回值即为公共节点，祖先的父节点的另一侧必定为null，
// 会一直返回公共祖先的值直到最上层
} else if (left != null) { // 左树有节点、右树无节点，返回左树
return left;
} else {
return right;
}
}
}
class Solution32 {
private TreeNode answer = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return this.answer;
}
public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean left = dfs(root.left, p, q);
boolean right = dfs(root.right, p, q);
if ((left && right) || ((root == p || root == q) && (left || right))) {
answer = root;
}
// 重点，我也不知道如何解释；当找到公共祖先后，祖先的父节点的另一侧必定为false，
// 不可能满足上面if判断，answer不可能被重新赋值
return left || right || root == p || root == q;
}
}
/**
* @date 2021 10 25
* 501.二叉搜索树中的众数
*/
class Solution31 {
List<Integer> ret = new ArrayList<>();
int base = 0;
int count = 0;
int maxCount = 0;
public int[] findMode(TreeNode root) {
dfs(root);
int[] resultArray = new int[ret.size()];
for (int i = 0; i < ret.size(); i++) {
resultArray[i] = ret.get(i);
}
return resultArray;
}
public void dfs(TreeNode root) {
if (root == null) return;
dfs(root.left);
update(root.val);
dfs(root.right);
}
public void update(int value) {
if (base == value) {
count++;
} else {
count = 1;
base = value;
}
if (count == maxCount) {
ret.add(value);
} else if (count > maxCount) {
maxCount = count;
ret.clear();
ret.add(value);
}
}
}
class Solution30 {
Map<Integer, Integer> frequency = new HashMap<>();
public int[] findMode(TreeNode root) {
inOrderTraverse(root);
int maxFreq = Integer.MIN_VALUE;
for (int i : frequency.keySet()) {
if (maxFreq < frequency.get(i)) {
maxFreq = frequency.get(i);
}
}
List<Integer> ret = new ArrayList<>();
for (int i : frequency.keySet()) {
if (maxFreq == frequency.get(i)) {
ret.add(i);
}
}
int[] res = new int[ret.size()];
for (int i = 0; i < res.length; i++) {
res[i] = ret.get(i);
}
return res;
}
public void inOrderTraverse(TreeNode root) {
if (root == null) return;
inOrderTraverse(root.left);
frequency.put(root.val, frequency.getOrDefault(root.val, 0) + 1);
inOrderTraverse(root.right);
}
}
/**
* 530. 二叉搜索树的最小绝对差
*/
class Solution29 {
public int getMinimumDifference(TreeNode root) {
List<Integer> val = new ArrayList<>();
inOrder(root, val);
int min = val.get(1) - val.get(0);
for (int i = 1; i < val.size() - 1; i++) {
if (val.get(i + 1) - val.get(i) < min) {
min = val.get(i + 1) - val.get(i);
}
}
return min;
}
public void inOrder(TreeNode root, List<Integer> ret) {
if (root == null) return;
inOrder(root.left, ret);
ret.add(root.val);
inOrder(root.right, ret);
}
}
/**
* 98. 验证二叉搜索树
*/
class Solution28 {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, int lower, int upper) {
if (root == null) return true;
if (root.val <= lower || root.val >= upper) {
return false;
}
return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
}
}
/**
* 700. 二叉搜索树中的搜索
*/
class Solution27 {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
TreeNode node = null;
if (root.val > val) {
node = searchBST(root.left, val);
} else {
node = searchBST(root.right, val);
}
return node;
}
}
/**
* 617. 合并二叉树
*/
class Solution26 {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
TreeNode node = null;
node = new TreeNode(root1.val + root2.val);
node.left = mergeTrees(root1.left, root2.left);
node.right = mergeTrees(root1.right, root2.right);
return node;
}
}
/**
* 654. 最大二叉树
*/
class Solution25 {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums.length <= 0) return null;
int maxI[] = getMaxIndex(nums);
TreeNode node = new TreeNode(maxI[0]);
int[] left = Arrays.copyOfRange(nums, 0, maxI[1]);
int[] right = Arrays.copyOfRange(nums, maxI[1] + 1, nums.length);
node.left = constructMaximumBinaryTree(left);
node.right = constructMaximumBinaryTree(right);
return node;
}
public int[] getMaxIndex(int[] nums) {
int max = nums[0];
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (max < nums[i]) {
index = i;
max = nums[i];
}
}
return new int[]{max, index};
}
}
/**
* 106. 从中序与后序遍历序列构造二叉树
*/
class Solution24 {
Map<Integer, Integer> memo = new HashMap<>();
int[] post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++) {
this.memo.put(inorder[i], i);
}
// 将值赋予全局变量，方便递归处理
this.post = postorder;
TreeNode root = buildTree(0, inorder.length - 1,
0, postorder.length - 1);
return root;
}
// 中序和后序的始末位置索引
public TreeNode buildTree(int inStart, int inEnd, int poStart, int poEnd) {
// 如果数量为空，直接返回;
// 如果相等，那还要把当前值生成一个对象，所以必须是 start > end;
if (inStart > inEnd || poStart > poEnd) {
return null;
}
// 找到根节点，并且找到中序的根节点的索引;
int curRoot = post[poEnd];
int curRootIndex = this.memo.get(curRoot); //中序的索引;
// 创建新的节点对象，将当前的值赋予node;
TreeNode node = new TreeNode(curRoot);
node.left = buildTree(inStart, curRootIndex - 1, poStart,
poStart + curRootIndex - inStart - 1);
node.right = buildTree(curRootIndex + 1, inEnd,
poStart + curRootIndex - inStart, poEnd - 1);
return node;
}
}
/**
* 113. 路径总和ii
*/
class Solution23 {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
findSum(root, targetSum);
return ret;
}
public void findSum(TreeNode root, int target) {
if (root == null) return;
path.add(root.val);
if (root.left == null && root.right == null && target == root.val) {
ret.add(new ArrayList<>(path)); //添加新的对象，否则列表一直引用的是同一个path对象；
}
findSum(root.left, target - root.val);
findSum(root.right, target - root.val);
path.remove(path.size() - 1); //回溯
}
}
/**
* 112. 路径总和
*/
class Solution22 {
// targetSum - root.val精髓所在
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.right == null && root.left == null) {
return targetSum == root.val;
}
boolean l = hasPathSum(root.left, targetSum - root.val);
boolean r = hasPathSum(root.right, targetSum - root.val);
return l || r;
}
public boolean pathSum(TreeNode root, int sum, int target) {
sum += root.val;
if (root.right == null && root.left == null && sum == target) {
return true;
}
boolean l = false;
boolean r = false;
if (root.left != null) {
l = pathSum(root.left, sum, target);
}
if (root.right != null) {
r = pathSum(root.right, sum, target);
}
return l || r;
}
}
/**
* 513. 找树左下角的值
*/
class Solution21 {
private int maxLevel = 0;
private int value = 0;
public int findBottomLeftValue(TreeNode root) {
value = root.val;
findLeftValue(root, 0);
return value;
}
public void findLeftValue(TreeNode root, int level) {
if (root == null) return;
if (root.right == null && root.left == null) {
if (level > maxLevel) {
maxLevel = level;
value = root.val;
}
return;
}
findLeftValue(root.left, level + 1);
findLeftValue(root.right, level + 1);
}
}
class Solution20 {
public int findBottomLeftValue(TreeNode root) {
int maxLevel = 0;
int value = 0;
Queue<TreeNode> levelNode = new LinkedList<>();
levelNode.offer(root);
while (!levelNode.isEmpty()) {
int size = levelNode.size();
TreeNode node = levelNode.peek();
value = node.val;
for (int i = 0; i < size; i++) {
node = levelNode.poll();
if (node.left != null) levelNode.offer(node.left);
if (node.right != null) levelNode.offer(node.right);
}
}
return value;
}
}
/**
* 404. 左叶子之和
*/
class Solution19 {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int sum = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
sum += sumOfLeftLeaves(root.left);
sum += sumOfLeftLeaves(root.right);
return sum;
}
}
/**
* 257. 二叉树的所有路径
*/
class Solution18 {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
constructPath(root, "", paths);
return paths;
}
public void constructPath(TreeNode root, String path, List<String> paths) {
if (root != null) {
StringBuilder pathSB = new StringBuilder(path);
pathSB.append(Integer.toString(root.val));
if (root.left == null && root.right == null) { //当前为叶子点
paths.add(pathSB.toString());
} else {
pathSB.append("->");
constructPath(root.left, pathSB.toString(), paths);
constructPath(root.right, pathSB.toString(), paths);
}
}
}
}
/**
* 110. 平衡二叉树
*/
class Solution17 {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return depth(root) >= 0;
}
public int depth(TreeNode root) {
if (root == null) return 0;
int l = depth(root.left);
int r = depth(root.right);
if (Math.abs(l - r) > 1 || l == -1 || r == -1) {
return -1;
} else {
// 返回子树的高度，用于下一层迭代的比较！靠终于懂了
return Math.max(r, l) + 1;
}
}
}
/**
* 222. 完全二叉树的节点个数
*/
class Solution16 {
public int countNodes(TreeNode root) {
if (root == null) return 0;
int sum = 0;
sum++;
sum += countNodes(root.left);
sum += countNodes(root.right);
return sum;
}
}
/**
* 104. 二叉树的最大深度
*/
class Solution15 {
public int maxDepth(Node root) {
if (root == null) return 0;
List<Integer> depth = new ArrayList<>();
for (Node child : root.children) {
depth.add(maxDepth(child));
}
if (depth.isEmpty()) return 1;
return Collections.max(depth) + 1;
}
}
/**
* 101. 对称二叉树
*/
class Solution14 {
public boolean isSymmetric(TreeNode root) {
if (root == null) return false;
return check(root.left, root.right);
}
public boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
} else if (left == null || right == null) {
return false;
} else {
if (left.val == right.val && check(left.left, right.right) && check(left.right, right.left)) {
return true;
}
return false;
}
}
}
/**
* 226. 翻转二叉树
*/
class Solution13 {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.right = left;
root.left = right;
return root;
}
}
/**
* 104. 二叉树的最大深度
*/
class Solution12 {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int maxDepth = 0;
Queue<TreeNode> levelNode = new LinkedList<>();
levelNode.offer(root);
while (!levelNode.isEmpty()) {
int size = levelNode.size();
for (int i = 0; i < size; i++) {
TreeNode node = levelNode.poll();
if (node.left != null) levelNode.offer(node.left);
if (node.right != null) levelNode.offer(node.right);
}
maxDepth++;
}
return maxDepth;
}
}
/**
* 116. 填充每个节点的下一个右侧节点指针
*/
//class Solution11 {
// public Node connect(Node root) {
// if (root == null) return null;
//
// Queue<Node> levelNode = new LinkedList<>();
// levelNode.offer(root);
//
// while (!levelNode.isEmpty()) {
// int size = levelNode.size();
//
// for (int i = 0; i < size; i++) {
// Node node = levelNode.poll();
// if (i != size - 1) {
// node.next = levelNode.peek();
// } else {
// node.next = null;
// }
// if (node.left != null) levelNode.offer(node.left);
// if (node.right != null) levelNode.offer(node.right);
// }
// }
//
//
// return root;
// }
//}
/**
* 515: 每个树行中找到层最大值
*/
class Solution10 {
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> levelNode = new LinkedList<>();
levelNode.offer(root);
while (!levelNode.isEmpty()) {
int levelSize = levelNode.size();
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < levelSize; i++) {
TreeNode node = levelNode.poll();
maxVal = Math.max(maxVal, node.val);
if (node.left != null) levelNode.offer(node.left);
if (node.right != null) levelNode.offer(node.right);
}
result.add(maxVal);
}
return result;
}
}
/**
* 429题：N叉树的层序遍历
*/
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {
}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
class Solution9 {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
Queue<Node> levelNode = new LinkedList<>();
levelNode.offer(root);
while (!levelNode.isEmpty()) {
int levelSize = levelNode.size();
List<Integer> levelValue = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
Node node = levelNode.poll();
levelValue.add(node.val);
levelNode.addAll(node.children);
// 等价于下面的for循环；forEach循环是否要判断null？
// int childSize = node.children.size();
// for (int j = 0; j < childSize; j++) {
// levelNode.offer(node.children.get(j));
// }
}
result.add(levelValue);
}
return result;
}
}
/**
* 637题：二叉树的层平均值、深度优先搜索
*/
class Solution8 {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> average = new ArrayList<>();
if (root == null) {
return average;
}
Deque<TreeNode> nodeStack = new LinkedList<>();
Deque<Integer> depthStack = new LinkedList<>();
nodeStack.push(root);
depthStack.push(0);
List<Integer> count = new ArrayList<>();
Map<Integer, Double> levelAndSum = new HashMap<>();
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
int depth = depthStack.pop();
if (node != null) {
if (depth < count.size()) {
count.set(depth, count.get(depth) + 1);
} else {
count.add(1);
}
// 设置Map的默认值
levelAndSum.put(depth, levelAndSum.getOrDefault(depth, 0.0) + node.val);
nodeStack.push(node.left);
depthStack.push(depth + 1);
nodeStack.push(node.right);
depthStack.push(depth + 1);
}
}
for (Integer integer : levelAndSum.keySet()) {
System.out.println(integer);
average.add(levelAndSum.get(integer) / count.get(integer));
}
return average;
}
}
/**
* 637题：二叉树的层平均值
*/
class Solution6 {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
Double sum = 0.0;
// List<Double> levelAverage = new ArrayList<>();
TreeNode node = null;
for (int i = 0; i < levelSize; i++) {
node = queue.poll();
// levelAverage.add((double) node.val);
sum += node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(sum / levelSize);
}
return result;
}
}
/**
* 199题：二叉树的右视图
*/
class Solution7 {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Map<Integer, Integer> rightMostValueDepth = new HashMap<>();
Deque<TreeNode> nodeStack = new LinkedList<>();
Deque<Integer> depthStack = new LinkedList<>();
nodeStack.push(root);
depthStack.push(0);
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
int depth = depthStack.pop();
if (node != null) {
if (!rightMostValueDepth.containsKey(depth)) {
rightMostValueDepth.put(depth, node.val);
}
nodeStack.push(node.left);
depthStack.push(depth + 1);
nodeStack.push(node.right);
depthStack.push(depth + 1);
}
}
// 学到了，直接addALL全部加进去，牛啊
result.addAll(rightMostValueDepth.values());
return result;
}
}
class Solution5 {
public List<Integer> rightSideView(TreeNode root) {
//存放结果的List表，用的ArrayList
List<Integer> result = new ArrayList<>();
if (root == null) return result;
//队列，用的LinkedList
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 层数节点值
int levelSize = queue.size();
TreeNode node = null;
for (int i = 0; i < levelSize; i++) {
node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(node.val);
}
return result;
}
}
class Solution4 {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 0; i < currentLevelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
Collections.reverse(result);
return result;
}
}
/**
* 前中后序遍历
* 递归
*/
class Solution1 {
List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preRecursion(root, result);
return result;
}
void preRecursion(TreeNode node, List<Integer> result) {
if (node == null) return;
// 前中后序遍历递归方法差不多
result.add(node.val);
preRecursion(node.left, result);
preRecursion(node.right, result);
}
}
/**
* 迭代方法；
*/
class Solution2 {
List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root == null) return result;
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode node = root;
// // 模拟栈的迭代，前序
// while (!stack.isEmpty() || node != null) {
// while (node != null) {
// result.add(node.val);
// stack.push(node);
// node = node.left;
// }
// stack.pop();
// node = node.right;
// }
// // 模拟栈的迭代，中序
// while (!stack.isEmpty() || node != null) {
// while (node != null) {
// stack.push(node);
// node = node.left;
// }
// stack.pop();
// result.add(node.val);
// node = node.right;
// }
// // 模拟栈的迭代，后序，左右中
// TreeNode prev = null;
//
// while (!stack.isEmpty() || node != null) {
// while (node != null) {
// stack.push(node);
// node = node.left;
// }
// node = stack.pop();
// if (node.right != null && root.right != prev) {
// stack.push(node);
// node = node.right;
// } else {
// result.add(node.val);
// prev = node;
// node = null;
// }
//
// }
return result;
}
}
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;
}
}