二叉数的先中后序统一遍历法
public static void preOrder(BiTree root){
BiTree p = root;
LinkedList<BiTree> stack = new LinkedList<>();
while(p != null || !stack.isEmpty()){
if(p != null){
System.out.print(p.val +"\t");
stack.push(p);
p = p.left;
}else {
p = stack.pop();
p = p.right;
}
}
}public static void preOrder00(BiTree root){
LinkedList<BiTree>stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
BiTree node = stack.peek();
if(node != null){
stack.pop();
if(node.right != null){
stack.push(node.right);
}
if(node.left !=null){
stack.push(node.left);
}
stack.push(node);
stack.push(null);
}else {
stack.pop();
BiTree p = stack.peek();
stack.pop();
System.out.print(p.val + "\t");
}
}
System.out.println();
}public static void preOrder03(BiTree root){
if(root == null){
return;
}
LinkedList<BiTree> stack = new LinkedList<>();
stack.push(root);
Map<BiTree,Boolean> visited = new HashMap<>();
while(!stack.isEmpty()){
BiTree node = stack.peek();
stack.pop();
if(visited.getOrDefault(node,false)){
System.out.print(node.val +"\t");
continue;
}
if(node.right != null){
stack.push(node.right);
visited.put(node.right, false);
}
if(node.left != null){
stack.push(node.left);
visited.put(node.left,false);
}
stack.push(node);
visited.put(node,true);
}
System.out.println("");
}
public static void inOrder(BiTree root){
LinkedList<BiTree> stack = new LinkedList<>();
BiTree p = root;
while( p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else {
p = stack.pop();
System.out.print(p.val + "\t");
p = p.right;
}
}
} public static void inOrder00(BiTree root){
LinkedList<BiTree> stack = new LinkedList<BiTree>();
stack.push(root);
while(!stack.isEmpty()){
BiTree node = stack.peek();
if(node != null){
stack.pop();
if(node.right != null){
stack.push(node.right);
}
stack.push(node);
stack.push(null);
if(node.left != null){
stack.push(node.left);
}
}else {
stack.pop();
node = stack.peek();
stack.pop();
System.out.print(node.val + "\t");
}
}
System.out.println();
}public static void inOrder03(BiTree root){
LinkedList<BiTree> stack = new LinkedList<>();
stack.push(root);
Map<BiTree,Boolean> isVisited = new HashMap<BiTree,Boolean>();
while(!stack.isEmpty()){
BiTree node = stack.peek();
stack.pop();
if(isVisited.getOrDefault(node, false)){
System.out.print(node.val +"\t");
continue;
}
if(node.right != null){
stack.push(node.right);
isVisited.put(node.right, false);
}
stack.push(node);
isVisited.put(node, false);
if(node.left != null){
stack.push(node.left);
isVisited.put(node.left, false);
}
isVisited.put(node, true);
}
}
public static void postOrder00(BiTree root){
LinkedList<BiTree> stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
BiTree p = stack.peek();
if(p != null){
stack.pop();
stack.push(p);
stack.push(null);
if(p.right != null){
stack.push(p.right);
}
if(p.left != null) {
stack.push(p.left);
}
}else {
stack.pop();
p = stack.peek();
System.out.print(p.val +"\t");
stack.pop();
}
}
System.out.println();
} public static void postOrder03(BiTree root){
LinkedList<BiTree> stack = new LinkedList<>();
BiTree p = root;
stack.push(p);
Map<BiTree,Boolean> isVisited = new HashMap<>();
while(!stack.isEmpty()){
BiTree node = stack.peek();
stack.pop();
if(isVisited.getOrDefault(node,false)){
System.out.print(node.val+"\t");
continue;
}
stack.push(node);
isVisited.put(node, true);
if(node.right != null){
stack.push(node.right);
isVisited.put(node.right, false);
}
if(node.left != null){
stack.push(node.left);
isVisited.put(node.left, false);
}
}
}public static void postOrder(BiTree root){
LinkedList<BiTree> stack = new LinkedList<BiTree>();
BiTree p = root;
BiTree r = null;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else {
p = stack.peek();
if (p.right != null && p.right != r) {
p = p.right;
} else {
p = stack.pop();
System.out.print(p.val + "\t");
r = p;
p = null;
}
}
}
}107.二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> results = new ArrayList<List<Integer>>();
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
if(root == null){
return results;
}
queue.offer(root);
while(!queue.isEmpty()){
int queueSize = queue.size();
List<Integer> result = new ArrayList<Integer>();
for(int i = 1; i <= queueSize; i++){
TreeNode node = queue.poll();
result.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
if(i == queueSize){
results.addFirst(result);
}
}
}
return results;
}199.二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
public List<Integer> rightSideView(TreeNode root) {
List<Integer> results= new ArrayList<Integer>();
if(root == null){
return results;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int queueSize = queue.size();
for(int i = 1; i <= queueSize; i++){
TreeNode node = queue.poll();
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
if(i == queueSize){
results.add(node.val);
}
}
}
return results;
}429.N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[ [1], [3,2,4], [5,6] ]
public List<List<Integer>> levelOrder(Node root) {
LinkedList<Node> queue = new LinkedList<Node>();
queue.offer(root);
List<List<Integer>> results = new ArrayList<List<Integer>>();
if(root == null){
return results;
}
while(!queue.isEmpty()){
List<Integer> result = new ArrayList<Integer>();
int levelSize = queue.size();
for(int i = 1; i <= levelSize; i++){
Node node = queue.poll();
result.add(node.val);
if(node.children != null){
for(int j = 0; j < node.children.size();j++){
queue.offer(node.children.get(j));
}
}
}
results.add(result);
}
return results;
}