package com.dengzm.jianzhioffer;
import java.util.ArrayDeque;
/**
* @Description 032 从上到下打印二叉树
* 从上到下打印二叉树的每个节点，同一层的节点按照从左到右的顺序打印
*
* Created by deng on 2019/5/23.
*/
public class Jianzhi032 {
public static void main(String[] args) {
BinaryTreeNode node1 = new BinaryTreeNode();
node1.value = 1;
BinaryTreeNode node2 = new BinaryTreeNode();
node2.value = 2;
BinaryTreeNode node3 = new BinaryTreeNode();
node3.value = 3;
BinaryTreeNode node4 = new BinaryTreeNode();
node4.value = 4;
BinaryTreeNode node5 = new BinaryTreeNode();
node5.value = 5;
BinaryTreeNode node6 = new BinaryTreeNode();
node6.value = 6;
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
printFromTopToBottom(node1);
}
private static void printFromTopToBottom(BinaryTreeNode root) {
if (root == null) {
return;
}
ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
BinaryTreeNode node = queue.pop();
printTreeNode(node);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
private static void printTreeNode(BinaryTreeNode node) {
if (node == null) {
return;
}
System.out.println(node.value);
}
}
package com.dengzm.jianzhioffer;
/**
* @Description 033 二叉搜索树的后序遍历序列
* 输入一个整数数组，判断数组是不是某二叉搜索树的后序遍历结果
*
* Created by deng on 2019/5/23.
*/
public class Jianzhi033 {
public static void main(String[] args) {
int[] squeue1 = new int[] {5,7,6,9,11,10,8};
int[] squeue2 = new int[] {5,7,6,9,11,10,8};
int[] squeue3 = new int[] {5,7,12,9,11,10,8};
int[] squeue4 = new int[] {12,7,6,9,11,10,8};
System.out.println(verifySqueceOfBST(squeue1, 0, squeue1.length - 1));
System.out.println(verifySqueceOfBST(squeue2, 0, squeue2.length - 1));
System.out.println(verifySqueceOfBST(squeue3, 0, squeue3.length - 1));
System.out.println(verifySqueceOfBST(squeue4, 0, squeue4.length - 1));
}
private static boolean verifySqueceOfBST(int[] sequeue, int start, int end) {
if (sequeue == null || sequeue.length == 0 || end < start) {
return false;
}
int root = sequeue[end];
// 在二叉搜索树中左子树的节点的值小于根节点的值
int i = start;
for (; i < end - start; i ++) {
if (sequeue[i] > root) {
break;
}
}
int j = i;
for (; j < end - start; j ++) {
if (sequeue[j] < root) {
return false;
}
}
boolean left = true;
if (i > start) {
left = verifySqueceOfBST(sequeue, start, i - 1);
}
boolean right = true;
if (i < end) {
right = verifySqueceOfBST(sequeue, i, end - 1);
}
return left && right;
}
}
package com.dengzm.jianzhioffer;
import java.util.Stack;
/**
* @Description 034 二叉树中和为某一值的路径
* 输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
*
* Created by deng on 2019/5/25.
*/
public class Jianzhi034 {
public static void main(String[] args) {
BinaryTreeNode node1 = new BinaryTreeNode(10);
BinaryTreeNode node2 = new BinaryTreeNode(5);
BinaryTreeNode node3 = new BinaryTreeNode(12);
BinaryTreeNode node4 = new BinaryTreeNode(4);
BinaryTreeNode node5 = new BinaryTreeNode(7);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
findPath(node1, 22);
}
/**
* 深度遍历的方式，找到所有符合结果的路径
*
* @param root root Node
* @param expectValue 符合该值的路径
*/
private static void findPath(BinaryTreeNode root, int expectValue) {
if (root == null) {
return;
}
Stack<Integer> path = new Stack<>();
int current = 0;
findPathCore(root, path, current, expectValue);
}
private static void findPathCore(BinaryTreeNode root, Stack<Integer> path, int currentValue, int expectValue) {
path.push(root.value);
currentValue += root.value;
// 值相等，且为一条完整路径（root到leaf）
if (currentValue == expectValue) {
boolean isLeaf = root.left == null && root.right == null;
if (isLeaf) {
System.out.print("Find a path : ");
for (Integer value : path) {
System.out.print(value + " ");
}
System.out.println();
}
}
if (root.left != null) {
findPathCore(root.left, path, currentValue, expectValue);
}
if (root.right != null) {
findPathCore(root.right, path, currentValue, expectValue);
}
// 在返回前，删除当前节点
path.pop();
}
}
