二叉树Binary Tree
1. 树的一些常用术语
2. 二叉树的概念
- 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树；
- 二叉树的子节点分为左子节点和右子节点；
- 以下三种均为二叉树：
- 若该二叉树的所有叶子节点都在最后一层，且节点总数n == \(2^k\) - 1，k为层数，则称为满二叉树。也即，满二叉树为：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。
- 若高度为k节点数为n的二叉树，对树中的节点按从上至下、从左至右的顺序进行编号，如果编号为i的节点与满二叉树中编号为i的节点在二叉树中的位置相同，则称为完全二叉树。也即，满二叉树是完全二叉树的特殊形态，一棵树是满二叉树必定是完全二叉树。
3. 二叉树的遍历
- 前序遍历：先输出父节点，再遍历左子树和右子树；
- 中序遍历：先遍历左子树，然后输出父节点，再遍历右子树；
- 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点。
- 注：判断前序、中序还是后序，看父节点输出的顺序。
3.1 前、中、后序遍历思路（递归）
- 创建一颗二叉树
- 创建TreeNode后通过setLeft和setRight方法建立各个节点的关系，并将root节点通过setRoot方法加入二叉树
- 前序遍历preorderTraversal（TreeNode root）
- 先输出当前节点（初始时是root节点）
- 若当前节点的左子节点不为空（即root.getLeft != null），则递归继续进行前序遍历
- 若当前节点的右子节点不为空（即root.getRight != null），则递归继续进行前序遍历
- 中序遍历inorderTraversal（TreeNode root）
- 若当前节点的左子节点不为空（即root.getLeft != null），则递归继续进行中序遍历
- 输出当前节点
- 若当前节点的右子节点不为空（即root.getRight != null），则递归继续进行中序遍历
- 后序遍历postorderTraversal（TreeNode root）
- 若当前节点的左子节点不为空（即root.getLeft != null），则递归继续进行后序遍历
- 若当前节点的右子节点不为空（即root.getRight != null），则递归继续进行后序遍历
- 输出当前节点
3.2 前、中、后序遍历代码实现（递归）
package com.datastructure;
/**
* @author SnkrGao
* @create 2023-04-26 19:22
*/
public class RecursiveTraversalBinaryTreeDemo {
public static void main(String[] args) {
BianryTree bianryTree = new BianryTree();
TreeNode root = new TreeNode(1, "宋江");
TreeNode node1 = new TreeNode(2, "吴用");
TreeNode node2 = new TreeNode(3, "卢俊义");
TreeNode node3 = new TreeNode(4, "林冲");
TreeNode node4 = new TreeNode(5, "关胜");
root.setLeft(node1);
root.setRight(node2);
node2.setLeft(node4);
node2.setRight(node3);
// 将root加入到二叉树中
bianryTree.setRoot(root);
System.out.println("前序遍历："); // 1，2，3，5，4
bianryTree.preorderTraversal(root);
System.out.println("中序遍历："); // 2，1，5，3，4
bianryTree.inorderTraversal(root);
System.out.println("后序遍历："); // 2，5，4，3，1
bianryTree.postorderTraversal(root);
}
}
class BianryTree {
private TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
public void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.println(root);
if (root.getLeft() != null) {
preorderTraversal(root.getLeft());
}
if (root.getRight() != null) {
preorderTraversal(root.getRight());
}
}
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
if (root.getLeft() != null) {
inorderTraversal(root.getLeft());
}
System.out.println(root);
if (root.getRight() != null) {
inorderTraversal(root.getRight());
}
}
public void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
if (root.getLeft() != null) {
postorderTraversal(root.getLeft());
}
if (root.getRight() != null) {
postorderTraversal(root.getRight());
}
System.out.println(root);
}
}
class TreeNode {
private int no;
private String name;
private TreeNode left;
private TreeNode right;
public TreeNode(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "TreeNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
3.3 前、中、后序遍历思路（非递归）
- 创建一颗二叉树
- 创建TreeNode后通过setLeft和setRight方法建立各个节点的关系，并将root节点通过setRoot方法加入到二叉树中
- 前序遍历preorderTraversal（TreeNode root）
- 建立一个辅助栈stack用于记录当前节点，以及一个辅助指针初始化为curNode = root
- 从根节点开始循环遍历树的每一个节点，当curNode == null且stack.isEmpty时，说明没有节点需要访问了，循环遍历结束
- 只要当前节点curNode != null，不断将当前节点压入栈中stack.push(curNode)，然后将当前节点作为父节点输出，再继续向其左子节点遍历curNode = curNode.getLeft（
先输出父节点再遍历左子树） - 当左子节点为空时，也即curNode == null，转向其右子节点进行访问。先将栈顶元素弹出找到curNode的父节点，然后进入该父节点的右子节点进行上一步的判断进行循环遍历，也即令curNode = stack.pop().getRight
- 只要当前节点curNode != null，不断将当前节点压入栈中stack.push(curNode)，然后将当前节点作为父节点输出，再继续向其左子节点遍历curNode = curNode.getLeft（
- 中序遍历inorderTraversal（TreeNode root）
- 建立一个辅助栈stack用于记录当前节点，以及一个辅助指针初始化为curNode = root
- 从根节点开始循环遍历树的每一个节点，当curNode == null且stack.isEmpty时，循环遍历结束
- 只要当前节点curNode != null，不断将当前节点压入栈中stack.push(curNode)，再继续向其左子节点遍历curNode = curNode.getLeft（
先遍历左子树） - 当左子节点为空时，也即curNode == null，转向其父节点进行输出后再转向其右子节点进行访问（
输出父节点再遍历右子树）。先将栈顶元素弹出找到curNode的父节点，将父节点输出，然后进入该父节点的右子节点进行上一步的判断进行循环遍历，也即令curNode = stack.pop().getRight
- 只要当前节点curNode != null，不断将当前节点压入栈中stack.push(curNode)，再继续向其左子节点遍历curNode = curNode.getLeft（
- 后序遍历postorderTraversal（TreeNode root）
- 建立一个辅助栈stack用于记录当前节点，以及一个辅助指针初始化为curNode = root，以及一个辅助指针记录上一个访问过的节点初始化为空visitedNode = null
- 从根节点开始循环遍历树的每一个节点，当curNode == null且stack.isEmpty时，循环遍历结束
- 只要当前节点curNode != null，不断将当前节点压入栈中stack.push(curNode)，再继续向其左子节点遍历curNode = curNode.getLeft（
先遍历左子树） - 当左子节点为空时，也即curNode == null，转向其右子节点。（
遍历右子树）- 先找到栈顶元素作为curNode的父节点并令curNode = stack.peek()
- 判断该父节点的右子节点是否为空或者是否已经被访问过
- 若curNode.getRight == null || curNode.getRight == visitedNode，将栈顶元素弹出并作为父节点输出（
最后输出父节点）。并记录该节点已经访问，即令visitedNode = stack.pop()。然后置curNode = null防止重复访问 - 若不满足上述判断条件，即右子节点没有被访问过，那么进入前述父节点curNode = stack.pop()的右子树继续进行前面的循环遍历访问，即令curNode = curNode.getRight
- 若curNode.getRight == null || curNode.getRight == visitedNode，将栈顶元素弹出并作为父节点输出（
- 只要当前节点curNode != null，不断将当前节点压入栈中stack.push(curNode)，再继续向其左子节点遍历curNode = curNode.getLeft（
3.4 前、中、后序遍历代码实现（非递归）
package com.datastructure;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* @author SnkrGao
* @create 2023-04-27 11:28
*/
public class NonRecursiveTraversalBinaryTreeDemo {
public static void main(String[] args) {
BinaryTree2 binaryTree2 = new BinaryTree2();
TreeNode2 root = new TreeNode2(1, "宋江");
TreeNode2 node1 = new TreeNode2(2, "吴用");
TreeNode2 node2 = new TreeNode2(3, "卢俊义");
TreeNode2 node3 = new TreeNode2(4, "林冲");
TreeNode2 node4 = new TreeNode2(5, "关胜");
root.setLeft(node1);
root.setRight(node2);
node2.setLeft(node4);
node2.setRight(node3);
// 将root加入到二叉树
binaryTree2.setRoot(root);
System.out.println("前序遍历："); // 1，2，3，5，4
binaryTree2.preorderTraversal(root);
System.out.println("中序遍历："); // 2，1，5，3，4
binaryTree2.inorderTraversal(root);
System.out.println("后序遍历："); // 2，5，4，3，1
binaryTree2.postorderTraversal(root);
}
}
class BinaryTree2 {
private TreeNode2 root;
public void setRoot(TreeNode2 root) {
this.root = root;
}
public void preorderTraversal(TreeNode2 root) {
if (root == null) {
return;
}
Deque<TreeNode2> stack = new ArrayDeque<>();
TreeNode2 curNode = root;
// 当当前节点为空且栈为空时，说明没有节点需要访问了，作为终止条件
while (curNode != null || !stack.isEmpty()) {
while (curNode != null) {
// 先输出父节点，再进入左子树
stack.push(curNode);
System.out.println(curNode);
curNode = curNode.getLeft();
}
// 当前节点（上一个父节点的左子节点）为空，转向父节点的右子树
if (!stack.isEmpty()) {
TreeNode2 tempNode = stack.pop(); // 找到父节点
curNode = tempNode.getRight();
}
}
}
public void inorderTraversal(TreeNode2 root) {
if (root == null) {
return;
}
Deque<TreeNode2> stack = new ArrayDeque<>();
TreeNode2 curNode = root;
while (curNode != null || !stack.isEmpty()) {
while (curNode != null) {
// 先遍历左子树
stack.push(curNode);
curNode = curNode.getLeft();
}
if (!stack.isEmpty()) {
// 输出父节点再遍历右子树
TreeNode2 tempNode = stack.pop();
System.out.println(tempNode);
curNode = tempNode.getRight();
}
}
}
public void postorderTraversal(TreeNode2 root) {
if (root == null) {
return;
}
Deque<TreeNode2> stack = new ArrayDeque<>();
TreeNode2 curNode = root;
TreeNode2 visitedNode = null; // 记录上一个访问过的节点
while (curNode != null || !stack.isEmpty()) {
while (curNode != null) {
// 先遍历左子树
stack.push(curNode);
curNode = curNode.getLeft();
}
// 当前节点（上一个父节点的左子节点）为空时，找到其父节点
curNode = stack.peek();
// 判断右子节点是否为空或已经被访问过
if (curNode.getRight() == null || curNode.getRight() == visitedNode) {
TreeNode2 tempNode = stack.pop();
System.out.println(tempNode);
visitedNode = tempNode; // 将该节点记录为上一个访问过的节点
curNode = null; // curNode置空，放置重复访问
} else {
// 遍历右子树
curNode = curNode.getRight();
}
}
}
}
class TreeNode2 {
private int no;
private String name;
private TreeNode2 left;
private TreeNode2 right;
public TreeNode2(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "TreeNode2{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
public TreeNode2 getLeft() {
return left;
}
public void setLeft(TreeNode2 left) {
this.left = left;
}
public TreeNode2 getRight() {
return right;
}
public void setRight(TreeNode2 right) {
this.right = right;
}
}
3.5 层序遍历思路
层序遍历就是逐层从左到右进行访问，当遍历完当前层时，再转到下一层的最左边的节点开始访问，重复上述过程完成对整棵二叉树的层序遍历。
- 建立一个队列queue，首先将根节点root入队列，即queue.offer(root)
- 利用队列先进先出的特点，访问完当前节点后，由于要先访问当前节点的右兄弟节点（即当前节点的父节点的右子节点，其此时位于队列头），因此先将当前节点的左右子节点放入队列尾，以便后续访问
- 当队列为空queue.isEmpty时结束循环遍历
- 否则，先输出此时队列头的节点tempNode = queue.poll()
- 判断tempNode的左子节点是否为空，若不为空则将其加入队列尾
- 判断tempNode的右子节点是否为空，若不为空则将其加入队列尾
3.6 层序遍历代码实现
public void levelorderTraversal(TreeNode2 root) {
if (root == null) {
return;
}
Queue<TreeNode2> queue = new LinkedList<>();
// 将root放入队列
queue.offer(root);
while (!queue.isEmpty()) { // 遍历终止条件是队列为空
// 队列头的节点出队列
TreeNode2 tempNode = queue.poll();
System.out.println(tempNode);
// 若其左子节点不为空，入队列尾
if (tempNode.getLeft() != null) {
queue.offer(tempNode.getLeft());
}
// 若其右子节点不为空，入队列尾
if (tempNode.getRight() != null) {
queue.offer(tempNode.getRight());
}
}
}
3.7 前序、中序遍历确定二叉树结构思路
-
前序遍历：根节点 -> 左子树 -> 右子树
中序遍历：左子树 -> 根节点 -> 右子树
-
根据前序遍历可以确定当前子树结构的根节点，即前序遍历序列的第一个元素root = new TreeNode(preorder[preLeft])
-
循环遍历中序遍历的序列，找到该根节点的位置，并在此过程中记录左子树的长度len。则根节点左侧的子序列为左子树，右侧的子序列为右子树
-
分别对左右子树递归执行上述步骤，找出左右子树的子树。直至preLeft > preRight || inLeft > inRight时递归结束。
- 递归setLeft：左子树的preorder子序列的起点为上一个root节点的下一位，即preLeft = preLeft + 1，终点为preRight = preLeft + len；左子树的inorder子序列的起点为inLeft，终点为找到的上一个root的前一位，即inRight = temInRight - 1
- 递归setRight：右子树的preorder子序列的起点为左子树终点的下一位，即preLeft = preLeft + len + 1，终点为preRight；右子树的inorder子序列的起点找到的为上一个root的后一位，即inLeft = tempInLeft + 1，终点为inRight
-
注意：前序、后序不能确定二叉树的原因在于：只知道根节点的位置，而缺少中序的信息，无法区分左子树和右子树。
3.8 前序、中序遍历确定二叉树结构代码实现
- 构建二叉树的方法代码
public TreeNode3 buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
public TreeNode3 buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) { // 递归终止
return null;
}
// preorder的第一位为当前子树的根节点
TreeNode3 root = new TreeNode3(preorder[preLeft]);
// 用于在inorder中移动的索引
int tempInLeft = inLeft;
// 左子树长度
int len = 0;
while (inorder[tempInLeft] != root.getNo()) {
tempInLeft++;
len++;
}
// 建立节点之间的关系
root.setLeft(buildTree(preorder, preLeft + 1, preLeft + len, inorder, inLeft, tempInLeft - 1));
root.setRight(buildTree(preorder, preLeft + len + 1, preRight, inorder, tempInLeft + 1, inRight));
// 返回根节点
return root;
}
- 包含输入输出信息的完整代码
package com.datastructure;
import java.util.*;
/**
* @author SnkrGao
* @create 2023-04-27 17:52
*/
public class PreorderInorderConstructBinaryTree {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入前序遍历序列：");
String preorderStr = scanner.next(); // 1,2,4,5,3,6,7,8
String[] preorderStrArr = preorderStr.split(",");
int[] preorder = new int[preorderStrArr.length];
for (int i = 0; i < preorder.length; i++) {
preorder[i] = Integer.parseInt(preorderStrArr[i]);
}
System.out.println("请输入中序遍历序列：");
String inorderStr = scanner.next(); // 4,2,5,1,3,7,6,8
String[] inorderStrArr = inorderStr.split(",");
int[] inorder = new int[inorderStrArr.length];
for (int i = 0; i < inorder.length; i++) {
inorder[i] = Integer.parseInt(inorderStrArr[i]);
}
BinaryTree3 binaryTree3 = new BinaryTree3();
binaryTree3.setRoot(binaryTree3.buildTree(preorder, inorder));
List<List<TreeNode3>> resList = binaryTree3.levelorderTraversal(binaryTree3.getRoot());
System.out.println(resList); // [[1],[2,3],[4,5,6],[7,8]]
}
}
class BinaryTree3 {
private TreeNode3 root;
public void setRoot(TreeNode3 root) {
this.root = root;
}
public TreeNode3 getRoot() {
return root;
}
public TreeNode3 buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
public TreeNode3 buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) { // 递归终止
return null;
}
// preorder的第一位为当前子树的根节点
TreeNode3 root = new TreeNode3(preorder[preLeft]);
// 用于在inorder中移动的索引
int tempInLeft = inLeft;
// 左子树长度
int len = 0;
while (inorder[tempInLeft] != root.getNo()) {
tempInLeft++;
len++;
}
// 建立节点之间的关系
root.setLeft(buildTree(preorder, preLeft + 1, preLeft + len, inorder, inLeft, tempInLeft - 1));
root.setRight(buildTree(preorder, preLeft + len + 1, preRight, inorder, tempInLeft + 1, inRight));
// 返回根节点
return root;
}
// 层序遍历的一种优化写法，将节点按层添加到list中返回
public List<List<TreeNode3>> levelorderTraversal(TreeNode3 root) {
if (root == null) {
return new ArrayList<>();
}
List<List<TreeNode3>> result = new ArrayList<>();
Queue<TreeNode3> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 每一层的遍历开始前记录队列中节点数量，即当前层的节点总数
int queueSize = queue.size();
List<TreeNode3> level = new ArrayList<>();
// for循环中的i无实际意义，只是为了一次性处理完当前层的所有节点
for (int i = 0; i < queueSize; i++) {
TreeNode3 tempNode = queue.poll();
level.add(tempNode);
if (tempNode.getLeft() != null) {
queue.offer(tempNode.getLeft());
}
if (tempNode.getRight() != null) {
queue.offer(tempNode.getRight());
}
}
result.add(level);
}
return result;
}
}
class TreeNode3 {
private int no;
private TreeNode3 left;
private TreeNode3 right;
public TreeNode3(int no) {
this.no = no;
}
@Override
public String toString() {
return "TreeNode3{" +
"no=" + no +
'}';
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public TreeNode3 getLeft() {
return left;
}
public void setLeft(TreeNode3 left) {
this.left = left;
}
public TreeNode3 getRight() {
return right;
}
public void setRight(TreeNode3 right) {
this.right = right;
}
}
4. 二叉树的前、中、后、序查找
4.1 前、中、后序查找思路
- 前序查找思路：
- 先判断当前节点的是否为要查找的节点，即判断root.getNo == searchNo是否成立
- 若相等说明已经找到，直接返回当前节点root
- 若不相等，判断root.getLeft是否为空，若不为空，向左递归执行前序查找
- 若向左递归前序查找找到了searchNode（searchNode != null），直接返回，不再执行后续的查找过程，否则searchNode会被向右递归查找的结果null覆盖
- 若没找到，继续判断root.getRight是否为空，若不为空，向右递归执行前序查找
- 先判断当前节点的是否为要查找的节点，即判断root.getNo == searchNo是否成立
- 中序查找思路：
- 先判断root.getLeft是否为空，若不为空，向左递归执行中序查找
- 若找到（searchNode != null），直接返回searchNode
- 若没找到，判断当前节点的是否为要查找的节点，即判断root.getNo == searchNo是否成立
- 若相等说明已经找到，直接返回当前节点root
- 若不相等，继续判断root.getRight是否为空，若不为空，向右递归执行中序查找
- 先判断root.getLeft是否为空，若不为空，向左递归执行中序查找
- 后序查找思路：
- 先判断root.getLeft是否为空，若不为空，向左递归执行后序查找
- 若找到（searchNode != null），直接返回searchNode
- 若没找到，继续判断root.getRight是否为空，若不为空，向右递归执行后序查找
- 若找到（searchNode != null），直接返回searchNode
- 若没找到，继续判断当前节点的是否为要查找的节点，若相等则返回当前节点root，没找到返回null
- 先判断root.getLeft是否为空，若不为空，向左递归执行后序查找
4.2 代码实现
package com.datastructure;
/**
* @author SnkrGao
* @create 2023-04-28 15:02
*/
public class BinaryTreeSearch {
public static void main(String[] args) {
BinaryTree4 binaryTree4 = new BinaryTree4();
TreeNode4 root = new TreeNode4(1, "宋江");
TreeNode4 node1 = new TreeNode4(2, "吴用");
TreeNode4 node2 = new TreeNode4(3, "卢俊义");
TreeNode4 node3 = new TreeNode4(4, "林冲");
TreeNode4 node4 = new TreeNode4(5, "关胜");
root.setLeft(node1);
root.setRight(node2);
node2.setLeft(node4);
node2.setRight(node3);
binaryTree4.setRoot(root);
int searchNo = 4;
System.out.println("前序查找：");
System.out.println(binaryTree4.preorderSearch(root, searchNo));
System.out.println("中序查找：");
System.out.println(binaryTree4.inorderSearch(root, searchNo));
System.out.println("后序查找：");
System.out.println(binaryTree4.postorderSearch(root, searchNo));
}
}
class BinaryTree4 {
private TreeNode4 root;
public void setRoot(TreeNode4 root) {
this.root = root;
}
public TreeNode4 preorderSearch(TreeNode4 root, int searchNo) {
if (root == null) {
return null;
}
// searchNode用于接收查找的结果
TreeNode4 searchNode = null;
if (root.getNo() == searchNo) {
return root;
}
if (root.getLeft() != null) {
// 这里递归调用不能直接return，因为回溯后还需要执行后面的语句，向右子树递归查找
searchNode = preorderSearch(root.getLeft(), searchNo);
}
// 若向左递归找到了searchNode，则直接return，不再继续向右递归，否则searchNode会被null覆盖
// 查找与遍历不同，遍历要把每一个节点都访问过，而查找只要找到就return
if (searchNode != null) {
return searchNode;
}
if (root.getRight() != null) {
searchNode = preorderSearch(root.getRight(), searchNo);
}
return searchNode;
}
public TreeNode4 inorderSearch(TreeNode4 root, int searchNo) {
if (root == null) {
return null;
}
TreeNode4 searchNode = null;
if (root.getLeft() != null) {
searchNode = inorderSearch(root.getLeft(), searchNo);
}
if (searchNode != null) {
return searchNode;
}
if (root.getNo() == searchNo) {
return root;
}
if (root.getRight() != null) {
searchNode = inorderSearch(root.getRight(), searchNo);
}
return searchNode;
}
public TreeNode4 postorderSearch(TreeNode4 root, int searchNo) {
if (root == null) {
return null;
}
TreeNode4 searchNode = null;
if (root.getLeft() != null) {
searchNode = postorderSearch(root.getLeft(), searchNo);
}
if (searchNode != null) {
return searchNode;
}
if (root.getRight() != null) {
searchNode = postorderSearch(root.getRight(), searchNo);
}
if (root.getNo() == searchNo) {
return root;
}
return searchNode;
}
}
class TreeNode4 {
private int no;
private String name;
private TreeNode4 left;
private TreeNode4 right;
public TreeNode4(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "TreeNode4{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public TreeNode4 getLeft() {
return left;
}
public void setLeft(TreeNode4 left) {
this.left = left;
}
public TreeNode4 getRight() {
return right;
}
public void setRight(TreeNode4 right) {
this.right = right;
}
}