Preorder traversal
Preorder traversal: middle -> left subtree -> right subtree
Non-recursive traversal-stack
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (null == root) {
return res;
}
LinkedList<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
if (null != node.right) {
stack.push(node.right);
}
if (null != node.left) {
stack.push(node.left);
}
}
return res;
}
morris
The space complexity is O(1)
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
TreeNode cur = root;
while (cur != null) {
// The left subtree is not null and is processed first.
if (null != cur.left) {
TreeNode leftMaxRight = cur.left;
while (leftMaxRight.right != null & amp; & amp; leftMaxRight.right != cur) {
leftMaxRight = leftMaxRight.right;
}
// leftMaxRight is a leaf node, right==null means that it needs to be continued; otherwise, it means that it has been processed and needs to be restored.
if (leftMaxRight.right == null) {
res.add(cur.val);
// Continue the connection, pointing to the next node in the in-order sort: leftMaxRight If it is the left subtree, then right=parent; if it is the right subtree, then right = the root.root of the tree where it is located
leftMaxRight.right = cur;
cur = cur.left;
continue;
} else {
// leftMaxRight is the leaf node, and the continued connection will restore the null value
leftMaxRight.right = null;
}
} else {
// 1) For non-leaf nodes, the left subtree is null, add cur directly, and then process its right subtree
// 2) The leaf node, the right subtree is the connection from the previous point, pointing to the next node in the in-order sorting
res.add(cur.val);
}
// 1) cur and its left subtree. After processing, process the right subtree
// 2) When cur is a leaf node, cur.right is the next node traversed in mid-order
cur = cur.right;
}
return res;
}
The connection on the traversal duration is as follows, pointing to the next node of in-order traversal, node5.right=node1, node4.right = node2
1: 5->1, output 1, enter 2
2: 4->2, output 2, enter 4
4: Output 4, enter 2
2: Disconnect 4->2, enter 5
5: Output 5, enter 1
1: Disconnect 5->1, enter 3
3: 6->3, output 3, enter 6
6: Output 6, enter 3
3: Disconnect 6->3, enter 7
7: Output 7
The final sequence is: 1, 2, 4, 5, 3, 6, 7
Topics covered:
https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/461821/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/?company_slug=meituan
Post-order traversal
Left subtree -> right subtree -> root
morris
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (null == root) {
return res;
}
TreeNode cur = root;
while (null != cur) {
if (null != cur.left) {
TreeNode leftMaxRight = cur.left;
while (leftMaxRight.right != null & amp; & amp; leftMaxRight.right != cur) {
leftMaxRight = leftMaxRight.right;
}
if (leftMaxRight.right == null) {
// Continuing from above, the next node of in-order traversal
leftMaxRight.right = cur;
cur = cur.left;
continue;
} else {
// Get rid of the continuation
leftMaxRight.right = null;
//The leaf node will only be processed when its parent is traversed for the second time.
addNodeRight(res, cur.left);
}
}
cur = cur.right;
}
// Process the last right subtree horizontal line
addNodeRight(res, root);
return res;
}
// Process the right subtree line starting from node
public void addNodeRight(List<Integer> res, TreeNode node) {
int left = res.size();
while (null != node) {
res.add(node.val);
node = node.right;
}
int right = res.size() - 1;
// left is the first insertion position, right is the last insertion position
// Reverse the left and right ranges
while (left < right) {
int tmp = res.get(left);
res.set(left, res.get(right));
res.set(right, tmp);
left + + ;
right--;
}
}
leetcode question address: https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/?company_slug=meituan
In-order traversal-morris
Reference preorder traversal
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
TreeNode cur = root;
while (cur != null) {
if (null != cur.left) {
TreeNode leftMaxRight = cur.left;
while (leftMaxRight.right != null & amp; & amp; leftMaxRight.right != cur) {
leftMaxRight = leftMaxRight.right;
}
if (leftMaxRight.right == null) {
leftMaxRight.right = cur;
cur = cur.left;
continue;
} else {
// Pre-order traversal cur puts res in if; mid-order traversal puts cur in else.
res.add(cur.val);
leftMaxRight.right = null;
}
} else {
res.add(cur.val);
}
cur = cur.right;
}
return res;
}