題目相關(guān)
題目要求為給定一個二叉樹，返回相應(yīng)的前序纹坐、中序耘子、后序遍歷球切。
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 迭代
使用了棧來實現(xiàn)迭代捍歪。
/**
* 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) {
//定義一個存放樹結(jié)點的棧糙臼、用于保存遍歷結(jié)果的list和指向當(dāng)前結(jié)點的變量curr
LinkedList<TreeNode> stack = new LinkedList<>();
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
//只有當(dāng)棧為空且當(dāng)前結(jié)點為NULL時才是遍歷結(jié)束恩商，其余情況都為遍歷中
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
//前序遍歷先將根結(jié)點的值放入list
list.add(curr.val);
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return list;
}
}
解法3 莫里斯遍歷
莫里斯遍歷的步驟為：
- 當(dāng)前結(jié)點指向根結(jié)點韧献，判斷二叉樹的根結(jié)點有沒有左子樹研叫，沒有則存儲該根結(jié)點的值嚷炉，當(dāng)前結(jié)點變?yōu)楦Y(jié)點的右孩子申屹。
- 如果第一步中有左子樹，判斷整個左子樹中最右邊的結(jié)點的右孩子是不是null
2.1 是null嚷那，存儲當(dāng)前節(jié)點的值杆煞，將該結(jié)點的右孩子指向當(dāng)前結(jié)點决乎，再將當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的左孩子
2.2 是當(dāng)前節(jié)點构诚，證明該結(jié)點與當(dāng)前結(jié)點已經(jīng)建立了連接，拆除連接恢復(fù)樹結(jié)構(gòu)送膳，再將當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的右孩子叠聋。
重復(fù)上述算法直到當(dāng)前結(jié)點為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;
//算法結(jié)束條件為當(dāng)前節(jié)點為null
while (curr != null) {
//if語句判斷算法第一步
if (curr.left == null) {
list.add(curr.val);
curr = curr.right;
} else {
//while循環(huán)與第一個if為算法的2.1脑慧，循環(huán)將pre指向左子樹的最右結(jié)點
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) {
pre = pre.right;
}
//pre的右孩子指向當(dāng)前結(jié)點
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();
//從最左邊的結(jié)點開始
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 {
//跟前序遍歷不同岩梳，中序遍歷在第二次遇到結(jié)點時存儲結(jié)點
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 迭代
后序遍歷的迭代思路跟前序和中序遍歷有一點小小的差別，迭代的一個解題的巧妙思路是：前序遍歷順序是根-左-右列疗，如果左子樹和右子樹遍歷的先后交換，得到根-右-左告材，最后輸出結(jié)果的時候逆序輸出可以得到左-右-根，剛好是后序遍歷的順序缰猴。
/**
* 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;
}
}
再進一步滑绒，可以不用逆序輸出蹬挤，而是在存儲結(jié)果的時候焰扳，不斷地將結(jié)點插入到上一個存儲的結(jié)點的前面误续，最后順序輸出結(jié)果也是后序遍歷的順序蹋嵌。在迭代的過程中栽烂，處理順序還是根-右-左的順序，但是存儲時不斷將結(jié)點放在上一個存儲的結(jié)點前面焰手，在list相當(dāng)于完成了左-右-根的順序书妻。這個思路是對上面一版代碼的優(yōu)化躬拢，更為巧妙聊闯。
/**
* 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) {
//存儲在上一個存儲的結(jié)點前面
list.addFirst(curr.val);
stack.push(curr);
curr = curr.right;
}
curr = stack.pop();
curr = curr.left;
}
return list;
}
}
那么在處理中就按照后序遍歷的左-右-根順序域慷，可以嗎犹褒？
自然是可以的弛针，不過有幾點值得注意的點削茁，按照左-右-根的順序遍歷，必須保證左孩子和右孩子都已經(jīng)被遍歷過慰丛，并且左孩子在右孩子之前遍歷才行诅病。
/**
* 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思路相同芥永，前序遍歷左右子樹的處理順序顛倒钝吮，最后的結(jié)果逆序棘催，得到后序遍歷链患。
/**
* 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叉樹麻捻，返回其節(jié)點值的后序遍歷郑叠。
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();
//把這個節(jié)點的所有孩子加入棧中，因為棧先進后出视粮，所有下次pop()得到的是最右邊的孩子蕾殴，符合根-右-左的順序
for( Node child : curr.children){
if(child != null){
stack.add(child);
}
}
list.add(curr.val);
}
//逆序一下
Collections.reverse(list);
return list;
}
}
