二叉树的遍历总结

• 144.二叉树的前序遍历(opens new window)
  
• 145.二叉树的后序遍历(opens new window)
  
• 94.二叉树的中序遍历
  

二叉数的先中后序同一遍历法

1. public static  void preOrder(BiTree root){
2.         BiTree p = root;
3.         LinkedList<BiTree> stack = new LinkedList<>();
4.         while(p != null || !stack.isEmpty()){
5.             if(p != null){
6.                 System.out.print(p.val +"\t");
7.                 stack.push(p);
8.                 p = p.left;
9.             }else {
10.                 p = stack.pop();
11.                 p = p.right;
12.             }
13.         }
14.     }

复制代码

1. public static  void preOrder00(BiTree root){
2.         LinkedList<BiTree>stack = new LinkedList<>();
3.         stack.push(root);
4.         while(!stack.isEmpty()){
5.             BiTree node = stack.peek();
6.             if(node != null){
7.                 stack.pop();
8.                 if(node.right != null){
9.                     stack.push(node.right);
10.                 }
11.                 if(node.left !=null){
12.                     stack.push(node.left);
13.                 }
14.                 stack.push(node);
15.                 stack.push(null);
16.             }else {
17.                 stack.pop();
18.                 BiTree p = stack.peek();
19.                 stack.pop();
20.                 System.out.print(p.val + "\t");
21.             }
22.         }
23.         System.out.println();
24.     }

复制代码

1. public  static void preOrder03(BiTree root){
2.         if(root == null){
3.             return;
4.         }
5.         LinkedList<BiTree> stack = new LinkedList<>();
6.         stack.push(root);
7.         Map<BiTree,Boolean> visited = new HashMap<>();
8.         while(!stack.isEmpty()){
9.             BiTree node = stack.peek();
10.             stack.pop();
11.             if(visited.getOrDefault(node,false)){
12.                 System.out.print(node.val +"\t");
13.                 continue;
14.             }
15.             if(node.right != null){
16.                 stack.push(node.right);
17.                 visited.put(node.right, false);
18.             }
19.             if(node.left != null){
20.                 stack.push(node.left);
21.                 visited.put(node.left,false);
22.             }
23.             stack.push(node);
24.             visited.put(node,true);
25.         }
26.         System.out.println("");
27.     }

复制代码

 

1. public static  void inOrder(BiTree root){
2.         LinkedList<BiTree> stack = new LinkedList<>();
3.         BiTree p = root;
4.         while( p != null || !stack.isEmpty()){
5.             if(p != null){
6.                 stack.push(p);
7.                 p = p.left;
8.             }else {
9.                 p = stack.pop();
10.                 System.out.print(p.val + "\t");
11.                 p = p.right;
12.             }
13.         }
14.     }

复制代码

1. public static void inOrder00(BiTree root){
2.         LinkedList<BiTree> stack = new LinkedList<BiTree>();
3.         stack.push(root);
4.         while(!stack.isEmpty()){
5.             BiTree node = stack.peek();
6.             if(node != null){
7.                 stack.pop();
8.                 if(node.right != null){
9.                     stack.push(node.right);
10.                 }
11.                 stack.push(node);
12.                 stack.push(null);
13.                 if(node.left != null){
14.                     stack.push(node.left);
15.                 }
16.             }else {
17.                 stack.pop();
18.                 node = stack.peek();
19.                 stack.pop();
20.                 System.out.print(node.val + "\t");
21.             }
22.         }
23.         System.out.println();
24.     }

复制代码

1. public static void inOrder03(BiTree root){
2.         LinkedList<BiTree> stack = new LinkedList<>();
3.         stack.push(root);
4.         Map<BiTree,Boolean> isVisited = new HashMap<BiTree,Boolean>();
5.         while(!stack.isEmpty()){
6.             BiTree node = stack.peek();
7.             stack.pop();
8.             if(isVisited.getOrDefault(node, false)){
9.                 System.out.print(node.val +"\t");
10.                 continue;
11.             }
13.             if(node.right != null){
14.                 stack.push(node.right);
15.                 isVisited.put(node.right, false);
16.             }
18.             stack.push(node);
19.             isVisited.put(node, false);
21.             if(node.left != null){
22.                 stack.push(node.left);
23.                 isVisited.put(node.left, false);
24.             }
25.             isVisited.put(node, true);
26.         }
27.     }

复制代码

 

1. public static void postOrder00(BiTree root){
2.         LinkedList<BiTree> stack = new LinkedList<>();
3.         stack.push(root);
4.         while(!stack.isEmpty()){
5.             BiTree p = stack.peek();
6.             if(p != null){
7.                 stack.pop();
8.                 stack.push(p);
9.                 stack.push(null);
10.                 if(p.right != null){
11.                     stack.push(p.right);
12.                 }
13.                 if(p.left != null) {
14.                     stack.push(p.left);
15.                 }
16.             }else {
17.                 stack.pop();
18.                 p = stack.peek();
19.                 System.out.print(p.val +"\t");
20.                 stack.pop();
21.             }
22.         }
23.         System.out.println();
24.     }

复制代码

1. public static void postOrder03(BiTree root){
2.         LinkedList<BiTree> stack = new LinkedList<>();
3.         BiTree p = root;
4.         stack.push(p);
5.         Map<BiTree,Boolean> isVisited = new HashMap<>();
6.         while(!stack.isEmpty()){
7.             BiTree node = stack.peek();
8.             stack.pop();
9.             if(isVisited.getOrDefault(node,false)){
10.                 System.out.print(node.val+"\t");
11.                 continue;
12.             }
13.             stack.push(node);
14.             isVisited.put(node, true);
16.             if(node.right != null){
17.                 stack.push(node.right);
18.                 isVisited.put(node.right, false);
19.             }
21.             if(node.left != null){
22.                 stack.push(node.left);
23.                 isVisited.put(node.left, false);
24.             }
25.         }
26.     }

复制代码

1. public static  void postOrder(BiTree root){
2.         LinkedList<BiTree> stack = new LinkedList<BiTree>();
3.         BiTree p = root;
4.         BiTree r = null;
5.         while(p != null || !stack.isEmpty()){
6.             if(p != null){
7.                 stack.push(p);
8.                 p = p.left;
9.             }else {
10.                 p = stack.peek();
11.                 if (p.right != null && p.right != r) {
12.                     p = p.right;
13.                 } else {
14.                     p = stack.pop();
15.                     System.out.print(p.val + "\t");
16.                     r = p;
17.                     p = null;
18.                 }
19.             }
20.         }
21.     }

复制代码

107.二叉树的条理遍历 II

力扣题目链接(opens new window)
给定一个二叉树，返回其节点值自底向上的条理遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 
 

1. public List<List<Integer>> levelOrderBottom(TreeNode root) {
2.         List<List<Integer>> results = new ArrayList<List<Integer>>();
3.         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
4.         if(root == null){
5.             return results;
6.         }
7.         queue.offer(root);
8.         while(!queue.isEmpty()){
9.             int queueSize = queue.size();
10.             List<Integer> result = new ArrayList<Integer>();
11.             for(int i = 1; i <= queueSize; i++){
12.                 TreeNode node = queue.poll();
13.                 result.add(node.val);
14.                 if(node.left != null){
15.                     queue.offer(node.left);
16.                 }
17.                 if(node.right != null){
18.                     queue.offer(node.right);
19.                 }
20.                 if(i == queueSize){
21.                     results.addFirst(result);
22.                 }
23.             }
24.         }
25.        return results;
26.     }

复制代码

199.二叉树的右视图

力扣题目链接(opens new window)
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

1. public List<Integer> rightSideView(TreeNode root) {
2.         List<Integer> results=  new ArrayList<Integer>();
3.         if(root == null){
4.             return results;
5.         }
6.         Queue<TreeNode> queue  = new LinkedList<TreeNode>();
7.         queue.offer(root);
8.         while(!queue.isEmpty()){
9.             int queueSize = queue.size();
10.             for(int i = 1; i <= queueSize; i++){
11.                 TreeNode node = queue.poll();
12.                 if(node.left != null){
13.                     queue.offer(node.left);
14.                 }
15.                 if(node.right != null){
16.                     queue.offer(node.right);
17.                 }
18.                 if(i == queueSize){
19.                     results.add(node.val);
20.                 }
21.             }
22.         }
23.         return results;
24.     }

复制代码

429.N叉树的层序遍历

力扣题目链接(opens new window)
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :

返回其层序遍历:
[ [1], [3,2,4], [5,6] ]

1. public List<List<Integer>> levelOrder(Node root) {
2.         LinkedList<Node> queue = new LinkedList<Node>();
3.         queue.offer(root);
4.         List<List<Integer>> results = new ArrayList<List<Integer>>();
5.         if(root == null){
6.             return results;
7.         }
8.         while(!queue.isEmpty()){
9.             List<Integer> result = new ArrayList<Integer>();
10.             int levelSize = queue.size();
11.             for(int i = 1; i <= levelSize; i++){
12.                 Node node = queue.poll();
13.                 result.add(node.val);
14.                 if(node.children != null){
15.                     for(int j = 0; j < node.children.size();j++){
16.                         queue.offer(node.children.get(j));
17.                     }
18.                 }
19.             }
20.             results.add(result);
21.         }
22.         return results;
23.     }

复制代码