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;
}
}