public class BinaryTreeTest {
public static void main(String[] args) {
TreeNode treeRootNode = BinaryTreeTest.createBinaryTreePreOrder(new LinkedList<>(Arrays.asList(3, 2, 9, null, null, 10, null)));
TreeNode treeRootNode2 = BinaryTreeTest.createBinaryTreePreOrder(new LinkedList<>(Arrays.asList(3, 2, 1, null, null, 10, null)));
// preOrderTravel(treeRootNode, "根");
// preOrderTravelByStack(treeRootNode);
// inorderTravel(treeRootNode, "根");
// postOrderTravel(treeRootNode, "根");
// postOrderTravelByStack(treeRootNode);
// perNodeAddOne(treeRootNode);
// System.out.println(isTwoTreeEqual(BinaryTreeTest.createBinaryTreePreOrder(new LinkedList<>(Arrays.asList(3, 2, 1, null, null, 10, null))), BinaryTreeTest.createBinaryTreePreOrder(new LinkedList<>(Arrays.asList(3, 2, 1, null, null, 10, null)))));
System.out.println(isBinarySearchTree(BinaryTreeTest.createBinaryTreePreOrder(new LinkedList<>(Arrays.asList(3, 2, 1, null, null, 10, null)))));
System.out.println(isValidBST(BinaryTreeTest.createBinaryTreePreOrder(new LinkedList<>(Arrays.asList(3, 2, 1, null, null, 10, null, null, 11, null, null)))));
System.out.println(isValidBST(BinaryTreeTest.createBinaryTreePreOrder(new LinkedList<>(Arrays.asList(3, 2, 11)))));
}
//是否是二叉排序树/二叉搜索树（任意左节点<根&&根的右子树，任意右节点>根&&根的左子树）！！右节点需要小于当前根节点的父节点
// 错误：(左值<根值<右值)
public static boolean isBinarySearchTree(TreeNode treeNode) {
if (treeNode == null) {
return true;
}
if (treeNode.leftNode != null && treeNode.leftNode.val >= treeNode.val) {
return false;
}
if (treeNode.rightNode != null && treeNode.val >= treeNode.rightNode.val) {
return false;
}
return isBinarySearchTree(treeNode.leftNode) && isBinarySearchTree(treeNode.rightNode);
}
static boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
static boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) return true;
System.out.println("root: " + root.val + ", min: " + (min == null ? "null" : min.val) + " , max : " + (max == null ? "null" : max.val));
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
return isValidBST(root.leftNode, min, root) && isValidBST(root.rightNode, root, max);//更新最大最小值的节点，往左分支，当前根一定是下面左节点的最大；往右分支，当前根一定是下面右节点的最小
}
//两颗二叉树相等
public static boolean isTwoTreeEqual(TreeNode tree1Node, TreeNode tree2Node) {
if ((tree1Node == null) != (tree2Node == null)) {
return false;
}
if (tree1Node == null) {
return true;
}
return tree1Node.val == tree2Node.val && isTwoTreeEqual(tree1Node.leftNode, tree2Node.leftNode) && isTwoTreeEqual(tree1Node.rightNode, tree2Node.rightNode);
}
//每个节点加一
public static void perNodeAddOne(TreeNode treeRootNode) {
if (treeRootNode == null) {
return;
}
TreeNode nodeTmp = treeRootNode;
nodeTmp.val++;
perNodeAddOne(nodeTmp.leftNode);
perNodeAddOne(nodeTmp.rightNode);
}
//前序构建二叉树
public static TreeNode createBinaryTreePreOrder(LinkedList<Integer> inputList) {
if (null == inputList || inputList.size() < 1) {
return null;
}
Integer data = inputList.removeFirst();
TreeNode node = null;
if (null != data) {
node = new TreeNode(data);//根
node.leftNode = createBinaryTreePreOrder(inputList);//左
node.rightNode = createBinaryTreePreOrder(inputList);//右
}
return node;
}
//前序遍历
public static void preOrderTravel(TreeNode treeRootNode, String index) {
if (treeRootNode == null) {
System.out.println("空 " + index);
return;
}
//根
System.out.println(treeRootNode.val + index);
//左
preOrderTravel(treeRootNode.leftNode, "左");
//右
preOrderTravel(treeRootNode.rightNode, "右");
}
//中序遍历
public static void inorderTravel(TreeNode treeRootNode, String index) {
if (null == treeRootNode) {
System.out.println("空 " + index);
return;
}
inorderTravel(treeRootNode.leftNode, "左");
System.out.println(treeRootNode.val + index);
inorderTravel(treeRootNode.rightNode, "右");
}
//后序遍历
public static void postOrderTravel(TreeNode treeNode, String index) {
if (null == treeNode) {
System.out.println("空 " + index);
return;
}
postOrderTravel(treeNode.leftNode, "左");
postOrderTravel(treeNode.rightNode, "右");
System.out.println(treeNode.val + index);
}
/**
* 栈实现前序遍历
*
* @param treeRootNode
*/
public static void preOrderTravelByStack(TreeNode treeRootNode) {
if (treeRootNode == null) {
return;
}
TreeNode rootNode = treeRootNode;
Stack<TreeNode> stack = new Stack<>();
while (rootNode != null || !stack.isEmpty()) {
//循环访问左节点
//前序：持续找左节点
while (rootNode != null) {
System.out.println(rootNode.val);
stack.push(rootNode);
rootNode = rootNode.leftNode;
System.out.println("left:" + rootNode);
}
{
System.out.println("空");
}
//前序：本次遍历，左节点为空，弹出栈顶的最近根节点，变访问节点为右节点
//没有左节点，弹出栈顶节点，访问右节点
if (!stack.isEmpty()) {
rootNode = stack.pop();
System.out.println(rootNode);
rootNode = rootNode.rightNode;
System.out.println("right:" + rootNode);
}
}
}
/**
* 栈实现后续遍历
* 与前序相同，仅输出位置不一致
*
* @param treeRootNode
*/
public static void postOrderTravelByStack(TreeNode treeRootNode) {
if (treeRootNode == null) {
return;
}
TreeNode rootNode = treeRootNode;
Stack<TreeNode> stack = new Stack<>();
while (rootNode != null || !stack.isEmpty()) {
//循环访问左节点
while (rootNode != null) {
System.out.println(rootNode.val);
stack.push(rootNode);
rootNode = rootNode.leftNode;
}
//没有左节点，弹出栈顶节点，访问右节点
if (!stack.isEmpty()) {
rootNode = stack.pop();
System.out.println("root:" + rootNode);
rootNode = rootNode.rightNode;
System.out.println("right:" + rootNode);
}
{
System.out.println("空");
}
}
}
//前序+标记是否出栈
public static void postOrderByStack(TreeNode node) {
if (node == null)
return;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = node;
TreeNode lastRoot = null;//标识是否已经出栈
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.leftNode;
}
//查询栈顶元素
cur = stack.peek();
//右子树为空或者右子树已经处理过，输出根
if (cur.rightNode == null || lastRoot == cur.rightNode) {
lastRoot = stack.pop();//出栈，标识是否已经处理过
System.out.print(lastRoot);
cur = null;
} else {
cur = cur.rightNode;
}
}
}
//队列
public static void levelOrderTravel(TreeNode node) throws InterruptedException {
if (node == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(node);
while (!queue.isEmpty()) {
TreeNode curNode = queue.poll();
System.out.println("levelOrderTravel:" + curNode);
if (curNode.leftNode != null) {
queue.offer(curNode.leftNode);
}
if (curNode.rightNode != null) {
queue.offer(curNode.rightNode);
}
}
}
private static class TreeNode {
private int val;
private TreeNode leftNode;
private TreeNode rightNode;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
@Override
public String toString() {
return "TreeNode{" +
"data=" + val +
'}';
}
}
}
网友评论