二叉树的存储方式和遍历方式

二叉树的存储方式

链式存储（指针）或 顺序存储（数组）

(1)链式存储：通过指针把分布在各个地址的节点串联一起。

(2)顺序存储：元素在内存是连续分布的，就是用数组来存储二叉树。
遍历方式：如果父节点的数组下标是 i，那么它的左孩子就是 2i + 1，右孩子 2i + 2，孩子的父节点为（i-1）/2。

链式存储的二叉树节点的定义方式（二叉树的定义和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子）

public class TreeNode {int val;TreeNode left; //表示左子节点的引用，类型为TreeNodeTreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

二叉树的遍历方式

• 广度优先遍历

  • 层次遍历（迭代法）

• 深度优先遍历

  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）

  

DFS–递归遍历

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}public void preorder(TreeNode root, List<Integer> result) {//     if (root != null) {//     result.add(root.val);//     preorder(root.left, result);//     preorder(root.right, result);//     }// }}

// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);             inorder(root.right, list);}
}

// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val);           }
}

DFS–迭代遍历

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();//必须要先判断，因为如果root==null，在执行 stack.push(root)时将会抛出空指针异常if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.right != null){stack.push(node.right);}if (node.left != null){stack.push(node.left);}}return result;}
}// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;//stack.push(root);(不能先把根节点入栈)while(cur != null || !stack.isEmpty()){// 尽可能深入左子树if(cur != null){stack.push(cur);cur = cur.left;}//当前节点为空，说明左子树已经遍历完毕，弹出栈顶元素,再处理右子树else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}// 后序遍历：先序遍历是中左右，我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result);return result;}
}

BFS–层次遍历 LC102

//BFS--迭代方式--借助队列  （题源）
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> resList = new ArrayList<>();if (root == null) {return resList;}//创建一个队列，使用 LinkedList 作为底层实现Queue<TreeNode> que = new LinkedList<>();que.offer(root);  //将元素插入到队尾while(!que.isEmpty()){List<Integer> itemList = new ArrayList<>();int levelSize = que.size();//for(int i = 0;i < que.size();i++)   不正确，因为for循环过程中size会变化for (int i = 0; i < levelSize; i++) {//移除并返回队列头部的元素,如果队列为空，则返回nullTreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if(tmpNode.left != null){que.offer(tmpNode.left);}if(tmpNode.right != null){ que.offer(tmpNode.right);}}resList.add(itemList);}return resList;}
}//BFS--递归方式
class Solution {List<List<Integer>> resList = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {// 初始层级为0，调用递归函数处理checkFun01(root, 0);return resList;}    public void checkFun01(TreeNode node, int deep) {if (node == null) {return;}deep++;//当层级增加时，确保resList中已经有足够的层级列表if (resList.size() < deep) {resList.add(new ArrayList<Integer>());}// 将当前节点值加入对应层级的列表中resList.get(deep - 1).add(node.val);// 递归处理左右子节点checkFun01(node.left, deep);checkFun01(node.right, deep);}
}LC107自底向上的层序遍历，就是在最后将集合翻转即可：Collections.reverse(resList);