二叉树的遍历算法

1.二叉树结构

2.广度优先搜索二叉树（迭代算法）

3.深度优先搜索二叉树（递归算法）

1.二叉树结构

一个父结点，至多可以连接左右两个子节点

Java构造树结构——其实是自定义树结点类型

 public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}TreeNode(int val,TreeNode lefTreeNode,TreeNode righTreeNode){this.val = val;left = lefTreeNode;right = righTreeNode;}}

2.广度优先搜索二叉树（迭代算法）

原理：（1）从上到下分层

（2）每层从左往右

解答：

（1）队列（先进先出）来迭代一层内的结点——更新队列，加入存在的左右子结点

（2）直到下一层无结点，循环再停止——该层队列为空

（3）每一层是检索上一层更新的队列，但队列可能会在本层有新增结点——检索前先记录上一层队列数量，按此数量，一个个弹出队头并检索。

以下是示范代码：

  public List<List<Integer>> levelOrder(TreeNode root) {ArrayDeque<TreeNode> deque = new ArrayDeque<TreeNode>();List<List<Integer>> compeleteList = new ArrayList<>();if (root == null) {return compeleteList;}deque.offer(root);while (!deque.isEmpty()) {List<Integer> arrList = new ArrayList<>();int dSize = deque.size();for(int i=0;i<dSize;++i ){TreeNode node = deque.poll();if (node.left != null) {deque.offer(node.left);}if (node.right != null) {deque.offer(node.right);}arrList.add(node.val);}compeleteList.add(arrList);}return compeleteList;}

3.深度优先搜索二叉树（递归算法）

这里以前序遍历为例子讲解：

当前结点-》左子结点1-》左子结点2-》右子结点2-》右子节点1

设计思路：

（1）哪里进入下一层

（2）给上一层返回什么

（3）最底层终止条件

下例：在记录本层数据后，无需返回上一层值，直到有结点为空停止。

    ArrayList<Integer> list = new ArrayList<>();public void preorder(TreeNode root){if (root == null) {return;}list.add(root.val);preorder(root.left);preorder(root.right);}