树的层次、前序、中序、后序遍历

1：前序遍历

《1递归思想：把根元素添加进列表，递归左边节点，递归右边节点

    public List<Integer> preorderTraversal(TreeNode root) {List<Integer>  result =new LinkedList<>();fuzhu(root,result);return result;}public void fuzhu(TreeNode root,List<Integer> result){if(root == null) return ;result.add(root.val);fuzhu(root.left,result);fuzhu(root.right,result);}

非递归思想：借助栈，当节点存入列表后，立即入栈，计算其左节点，下面循环外面用于弹栈计算其右节点

   public List<Integer> preorderTraversal(TreeNode root) {List<Integer> rs = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while (!stack.empty() || root != null) {while (root != null) {rs.add(root.val);stack.push(root);root = root.left;}root = stack.pop();root = root.right;}return rs;}

2：中序遍历

<1递归思想

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ls =new ArrayList<>();fuzhu(root,ls);return ls;}public void fuzhu(TreeNode root,List<Integer> ls){if(root==null)return;fuzhu(root.left,ls);ls.add(root.val);fuzhu(root.right,ls);}

《2非递归思想

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ls =new ArrayList<>();Stack<TreeNode> ss =new Stack();while(!ss.isEmpty() || root!=null){while(root!=null){ss.push(root);root=root.left;}root=ss.pop();ls.add(root.val);root=root.right;}return ls;}

3：后序遍历

<1递归思想

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ls = new ArrayList<>();fuzhu(root,ls);return ls;}public void fuzhu(TreeNode root,List<Integer> ls){if(root==null)return;fuzhu(root.left,ls);fuzhu(root.right,ls);ls.add(root.val);}

《2非递归思想：借助链表从后往前添加元素（其他方法待补充）

    public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();LinkedList<Integer> rs = new LinkedList<>();if (root == null) {return rs;}stack.push(root);while (!stack.empty()) {TreeNode temp = stack.pop();rs.addFirst(temp.val);if (temp.left != null) {stack.push(temp.left);}if (temp.right != null) {stack.push(temp.right);}}return rs;}

4：层次遍历

<1递归思想

    public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();addLevel(res,0,root);return res;}public void addLevel(List<List<Integer>> list, int level, TreeNode root) {if(root == null){return;}if(list.size() - 1 < level){list.add(new ArrayList<Integer>());}list.get(level).add(root.val);addLevel(list,level+1,root.left);addLevel(list,level+1,root.right);}

《2非递归思想：队列

    public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> levels = new ArrayList<>();if (root == null) {return levels;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int level = 0;while (!queue.isEmpty()) {levels.add(new ArrayList<>());int levelLength = queue.size();for (int i = 0; i < levelLength; ++i) {TreeNode node = queue.remove();levels.get(level).add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}level++;}return levels;}

借助一个队列存储节点，先把头节点放进去，输出当前节点值的同时，把当前节点的左右节点按顺序送进队列，只要队列不为空，就按先进先出弹出对应当前节点

    public static void LaywerTraversal(TreeNode root){if(root==null) return;LinkedList<TreeNode> list = new LinkedList<TreeNode>();list.add(root);TreeNode currentNode;while(!list.isEmpty()){currentNode=list.poll();System.out.println(currentNode.val);if(currentNode.left!=null){list.add(currentNode.left);}if(currentNode.right!=null){list.add(currentNode.right);}}}