目录
- 前序遍历
- 中序遍历
- 后序遍历
前序遍历
递归遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
traversal(ans, root);
return ans;
}
private void traversal(List<Integer> ans, TreeNode root) {
// 递归的结束条件。
if (null == root) {
return;
}
ans.add(root.val);
// 遍历左子树。
traversal(ans, root.left);
// 遍历右子树
traversal(ans, root.right);
}
迭代遍历
第一种方式
public List<Integer> preorderTraversal(TreeNode root) {
// 存放最终的结果。
List<Integer> ans = new LinkedList<>();
// 前序遍历使用的栈。
Deque<TreeNode> stack = new LinkedList<>();
while (!stack.isEmpty() || null != root) {
// 加入左节点.
while (null != root) {
stack.push(root);
// 因为是前序遍历将节点的值加入ans中。
ans.add(root.val);
root = root.left;
}
// 遍历右子树。
root = stack.pop().right;
}
return ans;
}
第二种方式
public List<Integer> preorderTraversal(TreeNode root) {
// 存储节点值的集合。
List<Integer> ans = new LinkedList<>();
// 二叉树为空，直接返回集合。
if (null == root) {
return ans;
}
// 遍历二叉树使用的栈。
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
// 前序遍历
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (null != node) {
// 压入右节点。
if (null != node.right) {
stack.push(node.right);
}
// 压入左节点。
if (null != node.left) {
stack.push(node.left);
}
// 压入根节点。
stack.push(node);
// 压入一个null值，作为分隔符。
stack.push(null);
} else {
// 当node=null的时候，将节点的值加入集合当中。
ans.add(stack.pop().val);
}
}
return ans;
}
Mirrors遍历
public List<Integer> preorderTraversal(TreeNode root) {
// 存储最终答案的集合。
List<Integer> ans = new LinkedList<>();
// Mirrors遍历使用的指针。
TreeNode p1 = root, p2 = null;
// Mirrors遍历
while (null != p1) {
p2 = p1.left;
if (null == p2) {
// 左子树为空，将结果加入集合，指针直接向右子树移动。
ans.add(p1.val);
} else {
// 左子树不为空，找到左子树的最右节点，判断该节点的右节点。
// 寻找最有节点。
while (null != p2.right && p1 != p2.right) {
p2 = p2.right;
}
// 如果最右节点的右节点是空。
if (null == p2.right) {
// 进行连接，将最右节点的右节点设置为当前节点。
p2.right = p1;
// 节点加入集合。
ans.add(p1.val);
// 当前节点往左移动。
p1 = p1.left;
continue;
} else {
// 最右节点的右节点不是null，指针向有移动，断开连接。
p2.right = null;
}
}
p1 = p1.right;
}
return ans;
}
中序遍历
递归遍历
public List<Integer> inorderTraversal(TreeNode root) {
// 存放节点的值。
List<Integer> ans = new LinkedList<>();
traversal(ans, root);
return ans;
}
private void traversal(List<Integer> ans, TreeNode root) {
// 递归结束条件。
if (null == root) {
return;
}
// 遍历左子树。
traversal(ans, root.left);
// 加入节点的值。
ans.add(root.val);
// 遍历右子树。
traversal(ans, root.right);
}
迭代遍历
第一种方式
public List<Integer> inorderTraversal(TreeNode root) {
// 存放结果的集合。
List<Integer> ans = new LinkedList<>();
// 遍历使用的栈
Deque<TreeNode> stack = new LinkedList<>();
// 中序遍历
while (!stack.isEmpty() || null != root) {
// 加入左节点。
while (null != root) {
stack.push(root);
root = root.left;
}
// 加入节点。
root = stack.pop();
// 将当前节点加入集合。
ans.add(root.val);
// 遍历右子树。
root = root.right;
}
return ans;
}
第二种方式
public List<Integer> inorderTraversal(TreeNode root) {
// 存放结果的集合。
List<Integer> ans = new LinkedList<>();
// 二叉树为空。
if (null == root) {
return ans;
}
// 遍历二叉树使用的栈。
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
// 中序遍历。
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (null != node) {
// 压入右节点。
if (null != node.right) {
stack.push(node.right);
}
// 压入当前节点。
stack.push(node);
// 压入null值作为分隔符。
stack.push(null);
// 压入左节点。
if (null != node.left) {
stack.push(node.left);
}
} else {
// 将节点加入集合。
ans.add(stack.pop().val);
}
}
return ans;
}
Mirrors遍历
public List<Integer> inorderTraversal(TreeNode root) {
// 存储答案的集合.
List<Integer> ans = new LinkedList<>();
// Mirrors遍历需要的指针
TreeNode p1 = root, p2 = null;
// Mirrors遍历
while (null != p1) {
p2 = p1.left;
if (null == p2) {
// 左子树为空。
// 将节点加入集合。
ans.add(p1.val);
} else {
// 左子树不为空，寻找中序前驱节点。
while (null != p2.right && p1 != p2.right) {
p2 = p2.right;
}
if (null == p2.right) {
// 前驱节点的右节点为空，将当前节点设置为前驱节点的右节点。
p2.right = p1;
// 节点向左移动。
p1 = p1.left;
continue;
} else {
// 前驱节点的右节点不为空，说明左子树已经遍历完成。
// 将当前节点加入集合。
ans.add(p1.val);
// 将前驱节点的右子树设置为null。
p2.right = null;
}
}
p1 = p1.right;
}
return ans;
}
后序遍历
递归遍历
public List<Integer> postorderTraversal(TreeNode root) {
// 存储结果的集合。
List<Integer> ans = new LinkedList<>();
traversal(ans, root);
return ans;
}
private void traversal(List<Integer> ans, TreeNode root) {
// 递归的结束条件。
if (null == root) {
return;
}
// 遍历左子树
traversal(ans, root.left);
// 遍历右子树
traversal(ans, root.right);
// 遍历根节点。
ans.add(root.val);
}
迭代遍历
第一种方式
public List<Integer> postorderTraversal(TreeNode root) {
// 存储结果的集合。
List<Integer> ans = new LinkedList<>();
// 遍历需要的栈。
Deque<TreeNode> stack = new LinkedList<>();
// 进行后序遍历。
while (!stack.isEmpty() || null != root) {
while (null != root) {
stack.push(root);
root = root.left;
}
root = stack.peek();
if (null != root) {
// 当前已经遍历完了左子树。
// 压入一个null作为标记。
stack.push(null);
// 不为空。
root = root.right;
} else {
// 为空，代表当前节点右子树已经遍历完成。
stack.pop();
ans.add(stack.pop().val);
root = null;
}
}
return ans;
}
第二种方式
public List<Integer> postorderTraversal(TreeNode root) {
// 存储结果的集合。
List<Integer> ans = new LinkedList<>();
// 二叉树为空。
if (null == root) {
return ans;
}
// 遍历二叉树使用的栈。
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
// 进行后序遍历。
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (null != node) {
// 压入根节点。
stack.push(node);
// 压入null作为当前节点已经访问过了。
stack.push(null);
// 压入右节点。
if (null != node.right) {
stack.push(node.right);
}
// 压入左节点。
if (null != node.left) {
stack.push(node.left);
}
} else {
// 如果为空，说明当前节点已经遍历完成。
ans.add(stack.pop().val);
}
}
return ans;
}
Mirrors遍历
public List<Integer> postorderTraversal(TreeNode root) {
// 存储结果的集合。
List<Integer> ans = new LinkedList<>();
// 为了遍历，常见一个虚拟节点。
TreeNode dummy = new TreeNode(0, root, null);
// Mirrors遍历需要的指针。
TreeNode p1 = dummy, p2 = null;
// 进行Mirrors遍历。
while (null != p1) {
p2 = p1.left;
// 当前节点的左子树为空的时候，直接向右子树移动。
if (null != p2) {
// 当前节点的左子树不为空。
// 寻找前驱节点。
while (null != p2.right && p1 != p2.right) {
p2 = p2.right;
}
if (null == p2.right) {
// 前驱节点的右子树为空，进行连接。
p2.right = p1;
// 指针向左移动。
p1 = p1.left;
continue;
} else {
// 前驱节点的右子树不为空，说明当前节点的已经访问完成了。
// 断开连接。
p2.right = null;
// 将从p1的左节点一直到前驱节点全部加入到集合当中。
addNode(ans, p1.left);
}
}
p1 = p1.right;
}
// 销毁哑节点。
dummy.left = null;
return ans;
}
private void addNode(List<Integer> ans, TreeNode root) {
// 获取集合当中已有元素的个数。
int size = ans.size();
// 倒序插入节点。
while (null != root) {
ans.add(size, root.val);
root = root.right;
}
}
note:后序遍历的Mirrors遍历，如果不使用容器，需要反转右子树。这样作者没有想到更完善的方法，如果有更好的方法，欢迎告诉作者。
作者目前只是一个自学编程的小白， 如果您发现文章又任何错误的地方，欢迎指出。
原创文章，作者：端木书台，如若转载，请注明出处：https://blog.ytso.com/269494.html