代码随想录算法跟练 | Day14

个人博客主页：http://myblog.nxx.nx.cn
代码GitHub地址：https://github.com/nx-xn2002/Data_Structure.git

Day14

今天，主要是二叉树的基础知识，包括二叉树的结构、存储方式和遍历方式

二叉树的结构

二叉树顾名思义，就是由一个或多个节点组成的树形结构，树形结构中起始的节点被称为根节点，而二叉则表示每个节点有两个子节点，通常将一个节点的左右节点为根节点构成的树称为这个节点的左子树和右子树，如果一个节点的左子树和右子树都为空，它被称为二叉树的叶子结点。

二叉树的存储方式

链式存储

这是我们平时最常见的二叉树的存储方式，每个节点上存储了当前节点的值，还有左右指针分别指向左右子树的根节点的地址。

class TreeNode{int data;TreeNode left;TreeNode right;
}

顺序存储

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2，按这样的规律进行存储，结果类似二叉树的层序遍历

二叉树的遍历方式

二叉树主要有两种遍历方式：

深度优先遍历：优先向深处走，遍历到一条路径的叶子结点后，再遍历其他路径
广度优先遍历：按照深度划分层次，按层次逐渐向下遍历

深度优先遍历

深度优先遍历按照遍历当前节点的先后次序，分为了三种：

前序遍历（中 -> 左 -> 右）
中序遍历（左 -> 中 -> 右）
后序遍历（左 -> 右 -> 中）

我们可以很容易地使用递归来实现这几种遍历方式：

/**
* 前序遍历
*/
public void traversal1(TreeNode root){if(root == null){return;}System.out.println(root.data);traversal(root.left);traversal(root.right);
}/**
* 中序遍历
*/
public void traversal2(TreeNode root){if(root == null){return;}traversal(root.left);System.out.println(root.data);traversal(root.right);
}/**
* 后序遍历
*/
public void traversal3(TreeNode root){if(root == null){return;}traversal(root.left);traversal(root.right);System.out.println(root.data);
}

而相对应的，递归可以通过栈加循环的方式转换为迭代，迭代法如下所示：

/**
* 前序遍历
*/
public List<Integer> traversal1(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null){return res;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){//中TreeNode temp = stack.peek();stack.pop();res.add(temp.data);//右if(temp.right != null){stack.push(temp.right);}//左if(temp.left != null){stack.push(temp.left);}}return res;
}/**
* 中序遍历
*/
public List<Integer> traversal2(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null){return res;}Stack<TreeNode> stack = new Stack<>();stack.push(root);TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();res.add(cur.data);cur = cur.right;}}return res;
}/**
* 后序遍历
*/
public List<Integer> traversal3(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null){return res;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){//中TreeNode temp = stack.peek();stack.pop();res.add(temp.data);//左if(temp.left != null){stack.push(temp.left);}//右if(temp.right != null){stack.push(temp.right);}}Collections.reverse(res);return res;
}

广度优先遍历

广度优先遍历在树形结构中也称为层序遍历，实现思路也比较简单，只需要使用一个队列来进行辅助，先将某一层的所有节点放到队列中，队首出队操作即为对队首元素指向的节点进行遍历，同时依次将队首的非空左右指针入队，这样当某一层元素遍历完毕后，也完成了对下一层所有元素的入队操作。

代码实现：

public List<List<Integer>> traversal(TreeNode node) {List<List<Integer>> res = new ArrayList<>();if(node == null){return res;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(node);while (!queue.isEmpty()) {List<Integer> itemList = new ArrayList<Integer>();int len = queue.size();while (len > 0) {TreeNode tmpNode = queue.poll();itemList.add(tmpNode.data);if (tmpNode.left != null){que.offer(tmpNode.left);}if (tmpNode.right != null){que.offer(tmpNode.right);}len--;}res.add(new ArrayList<>(itemList));}
}