题目相关
题目要求为给定一个二叉树，返回相应的前序、中序、后序遍历。
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
前序遍历
解法1 递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
QX(root, list);
return list;
}
//前序遍历是根-左-右的顺序
public void QX(TreeNode root, List<Integer> list) {
if (root != null) {
list.add(root.val);
if (root.left != null) {
QX(root.left, list);
}
if (root.right != null) {
QX(root.right, list);
}
}
}
}
解法2 迭代
使用了栈来实现迭代。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//定义一个存放树结点的栈、用于保存遍历结果的list和指向当前结点的变量curr
LinkedList<TreeNode> stack = new LinkedList<>();
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
//只有当栈为空且当前结点为NULL时才是遍历结束，其余情况都为遍历中
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
//前序遍历先将根结点的值放入list
list.add(curr.val);
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return list;
}
}
解法3 莫里斯遍历
莫里斯遍历的步骤为：
- 当前结点指向根结点，判断二叉树的根结点有没有左子树，没有则存储该根结点的值，当前结点变为根结点的右孩子。
- 如果第一步中有左子树，判断整个左子树中最右边的结点的右孩子是不是null
2.1 是null，存储当前节点的值，将该结点的右孩子指向当前结点，再将当前结点更新为当前结点的左孩子
2.2 是当前节点，证明该结点与当前结点已经建立了连接，拆除连接恢复树结构，再将当前结点更新为当前结点的右孩子。
重复上述算法直到当前结点为null。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
//算法结束条件为当前节点为null
while (curr != null) {
//if语句判断算法第一步
if (curr.left == null) {
list.add(curr.val);
curr = curr.right;
} else {
//while循环与第一个if为算法的2.1，循环将pre指向左子树的最右结点
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) {
pre = pre.right;
}
//pre的右孩子指向当前结点
if (pre.right == null) {
pre.right = curr;
list.add(curr.val);
curr = curr.left;
} else {
//算法的2.2
pre.right = null;
curr = curr.right;
}
}
}
return list;
}
}
中序遍历
跟前序遍历主要是顺序差别
解法1 递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
ZX(root, list);
return list;
}
//中序遍历：左-根-右
public void ZX(TreeNode root, List<Integer> list) {
if (root != null) {
if (root.left != null) {
ZX(root.left, list);
}
list.add(root.val);
if (root.right != null) {
ZX(root.right, list);
}
}
}
}
解法2 迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
while ((!stack.isEmpty()) || (curr != null)) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
//从最左边的结点开始
list.add(curr.val);
curr = curr.right;
}
return list;
}
}
解法3 莫里斯遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
list.add(curr.val);
curr = curr.right;
} else {
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = curr;
curr = curr.left;
} else {
//跟前序遍历不同，中序遍历在第二次遇到结点时存储结点
pre.right = null;
list.add(curr.val);
curr = curr.right;
}
}
}
return list;
}
}
后序遍历
解法1 递归
递归注意顺序就好。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
HX(root, list);
return list;
}
//后序遍历顺序为左-右-根
public void HX(TreeNode root, List<Integer> list) {
if (root != null) {
if (root.left != null) {
HX(root.left, list);
}
if (root.right != null) {
HX(root.right, list);
}
list.add(root.val);
}
}
}
解法2 迭代
后序遍历的迭代思路跟前序和中序遍历有一点小小的差别，迭代的一个解题的巧妙思路是：前序遍历顺序是根-左-右，如果左子树和右子树遍历的先后交换，得到根-右-左，最后输出结果的时候逆序输出可以得到左-右-根，刚好是后序遍历的顺序。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
//先右子树
list.add(curr.val);
stack.push(curr);
curr = curr.right;
}
curr = stack.pop();
//再左子树
curr = curr.left;
}
//逆序
Collections.reverse(list);
return list;
}
}
再进一步，可以不用逆序输出，而是在存储结果的时候，不断地将结点插入到上一个存储的结点的前面，最后顺序输出结果也是后序遍历的顺序。在迭代的过程中，处理顺序还是根-右-左的顺序，但是存储时不断将结点放在上一个存储的结点前面，在list相当于完成了左-右-根的顺序。这个思路是对上面一版代码的优化，更为巧妙。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> list = new LinkedList<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
//存储在上一个存储的结点前面
list.addFirst(curr.val);
stack.push(curr);
curr = curr.right;
}
curr = stack.pop();
curr = curr.left;
}
return list;
}
}
那么在处理中就按照后序遍历的左-右-根顺序，可以吗？
自然是可以的，不过有几点值得注意的点，按照左-右-根的顺序遍历，必须保证左孩子和右孩子都已经被遍历过，并且左孩子在右孩子之前遍历才行。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
TreeNode s = null;
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
//peek()返回栈顶元素，不在栈中删除它
curr = stack.peek();
if (curr.right == null || curr.right == s) {
list.add(curr.val);
stack.pop();
s = curr;
curr = null;
} else {
curr = curr.right;
}
}
return list;
}
}
解法3 莫里斯遍历
与解法2思路相同，前序遍历左右子树的处理顺序颠倒，最后的结果逆序，得到后序遍历。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.right == null) {
list.add(curr.val);
curr = curr.left;
} else {
TreeNode pre = curr.right;
while (pre.left != null && pre.left != curr) {
pre = pre.left;
}
if (pre.left == null) {
pre.left = curr;
list.add(curr.val);
curr = curr.right;
}
if (pre.left == curr) {
pre.left = null;
curr = curr.left;
}
}
}
Collections.reverse(list);
return list;
}
}
题目描述
给定一个N叉树，返回其节点值的后序遍历。
590. N叉树的后序遍历
解法 迭代
思路是根-右-左，最后逆序得到后序遍历。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
Stack<Node> stack = new Stack<>();
ArrayList<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
stack.add(root);
while(!stack.isEmpty()){
Node curr = stack.pop();
//把这个节点的所有孩子加入栈中，因为栈先进后出，所有下次pop()得到的是最右边的孩子，符合根-右-左的顺序
for( Node child : curr.children){
if(child != null){
stack.add(child);
}
}
list.add(curr.val);
}
//逆序一下
Collections.reverse(list);
return list;
}
}
