94. 二叉樹的中序周遊
遞歸法
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
mid(root);
return res;
}
public void mid(TreeNode root){
if(root == null){
return;
}
if(root.left != null){
mid(root.left);
}
res.add(root.val);
if(root.right != null){
mid(root.right);
}
}
}
棧疊代
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stk = new LinkedList<TreeNode>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
Morris算法
- 如果x無左孩子,先将x放入數組,再x = x.right
- 如果x有左孩子,找到x左子樹最右的節點(左子樹中序周遊的最後一個節點,x在中序周遊的前驅節點),記作predecessor
- 如果predecessor的右孩子為空,則将其右孩子指向x,然後x = x.left
- 如果predecessor的右孩子不為空,說明我們已經周遊完了x的左子樹,将其右孩子置空,将x放入數組,x = x.right
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
TreeNode predecessor = null;
while (root != null) {
if (root.left != null) {
// predecessor 節點就是目前 root 節點向左走一步,然後一直向右走至無法走為止
predecessor = root.left;
while (predecessor.right != null && predecessor.right != root) {
predecessor = predecessor.right;
}
// 讓 predecessor 的右指針指向 root,繼續周遊左子樹
if (predecessor.right == null) {
predecessor.right = root;
root = root.left;
}
// 說明左子樹已經通路完了,我們需要斷開連結
else {
res.add(root.val);
predecessor.right = null;
root = root.right;
}
}
// 如果沒有左孩子,則直接通路右孩子
else {
res.add(root.val);
root = root.right;
}
}
return res;
}
}