二叉树的遍历总结

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

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

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

力扣题目链接(opens new window)

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 

 

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.二叉树的右视图

力扣题目链接(opens new window)

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

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叉树的层序遍历

力扣题目链接(opens new window)

给定一个 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;}