二叉树遍历

扯犊子：具体的思路我就不写了，代码贴出来，如果有需要的话可以私聊

初级菜鸟，如果缺点望指出，多多沟通，有利于成长。

树的结构

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

public class Demo_08 { // 深度 public int maxDepth(TreeNode root) { if (root == null) return 0; else { int left = maxDepth(root.left); int right = maxDepth(root.right); return 1 + Math.max(left, right); } } public static void main(String[] args) { TreeNode t1 = new TreeNode(1); TreeNode t2 = new TreeNode(2); TreeNode t3 = new TreeNode(3); TreeNode t4 = new TreeNode(4); TreeNode t5 = new TreeNode(5); TreeNode t6 = new TreeNode(6); TreeNode t7 = new TreeNode(7); TreeNode t8 = new TreeNode(8); TreeNode t9 = new TreeNode(9); TreeNode t10 = new TreeNode(10); t1.left = t2; t1.right = t3; t2.left = t4; t2.right = t5; t3.left = t6; t3.right = t7; t5.left = t8; t5.right = t9; t9.left = t10; List<Integer> list = new ArrayList<Integer>(); Demo_08 d = new Demo_08(); list = d.postOrderBinary(t1, list); int i = d.maxDepth(t1); System.out.println(i); System.out.println(list); System.out.println(max); } /* * 前序遍历 高度 */ static int max = 0; public List<Integer> preOrderBinary(TreeNode root, List<Integer> list) { if (root == null) return list; TreeNode node = root; Stack<TreeNode> s = new Stack<TreeNode>(); while (node != null || s.size() != 0) { while (node != null) { s.push(node); list.add(node.val); node = node.left; } if (s.size() > max) max = s.size(); node = s.pop(); node = node.right; } return list; } /* * 中序遍历 */ public List<Integer> inOrderBinary(TreeNode root, List<Integer> list) { if (root == null) return list; TreeNode node = root; Stack<TreeNode> s = new Stack<TreeNode>(); while (node != null || s.size() != 0) { while (node != null) { s.push(node); node = node.left; } node = s.pop(); list.add(node.val); node = node.right; } return list; } /* * 后续遍历 */ public List<Integer> postOrderBinary(TreeNode root, List<Integer> list) { if (root == null) return list; TreeNode node = root; Stack<TreeNode> s = new Stack<TreeNode>(); Stack<Integer> f = new Stack<Integer>(); int te = 0; while (node != null || s.size() != 0) { while (node != null) { s.push(node); f.push(1); node = node.left; } node = s.pop(); te = f.pop(); if (te == 1) { s.push(node); f.push(0); node = node.right; } else { list.add(node.val); node = null; } } return list; } /* * 层次遍历 */ public List<Integer> levelTraverseBinary(TreeNode root, List<Integer> list) { if (root == null) return list; TreeNode node = root; List<TreeNode> pNode = new ArrayList<TreeNode>(); pNode.add(node); while (node != null && pNode.size() != 0) { node = pNode.remove(0); if (node != null) list.add(node.val); if (node.left != null) pNode.add(node.left); if (node.right != null) pNode.add(node.right); } return list; } }