Today we write three types of binary tree traversal, recursive, iterative, and Morris traversal. In principle, there are 9 kinds of traversal. However, Morris traversal is not used to write the sequence traversal, which is more complicated and has more operation times.
LeetCode 144 Binary Tree Preorder Traversal
Link: leetcode.com/problems/bi…
Method 1: Recursion
Time complexity: O(n)
Space complexity: O(h), at worst O(n), does not count as a result array, and the following space complexity analysis does not count as a result array
Idea: The most basic recursion is res.add() before calling left and right.
Code:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root, res);
return res;
}
private void preOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return; } res.add(root.val); preOrder(root.left, res); preOrder(root.right, res); }}Copy the codeMethod 2: iteration, stack
Time complexity: O(n)
Space complexity: O(h) at worst O(n)
Idea: Use a stack to simulate recursion, since recursion is written by moving the left subtree first and then the right subtree, but the stack is LIFO, so node.right should be pushed first and Then Node. left.
Code:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root ! =null) {
stack.push(root);
}
while(! stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val);if(node.right ! =null) {
stack.push(node.right);
}
if(node.left ! =null) { stack.push(node.left); }}returnres; }}Copy the codeMorris Traversal
Time complexity: O(n)
Space complexity: O(1)
Idea: This Morris traversal can be simulated with a few examples. So the main thing for me to brush the interview is to remember Morris traversal principle and write code. The content of the reference posts zhuanlan.zhihu.com/p/101321696 and www.acwing.com/blog/conten… .
Morris traversal rules: Assume that the current node is root
- if
root.left == null,root = root.rightThe continue directly, - if
root.left ! = null, to find all the way to the right-most node of root’s left subtree, which is its precursor, denoted as mostRight- If the right pointer to mostRight points to null, make it point to root, then
cur=cur.left - If the right pointer to mostRight points to root, let it point to null, then
cur=cur.right
- If the right pointer to mostRight points to null, make it point to root, then
The first point of the second point is called bridge construction, and the second point of the second point is called bridge removal. PreOrder Traversal inserts elements into the result array, which needs to be done at the bridge stage. For inOrder Traversal it is required to remove the bridge.
Code:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
while(root ! =null) {
if (root.left == null) {
res.add(root.val);
root = root.right;
}
else {
TreeNode mostRight = root.left;
while(mostRight.right ! =null&& mostRight.right ! = root) { mostRight = mostRight.right; }if (mostRight.right == null) {
mostRight.right = root;
res.add(root.val);
root = root.left;
}
else {
mostRight.right = null; root = root.right; }}}returnres; }}Copy the codeLeetCode 94 Binary Tree Inorder Traversal
Link: leetcode.com/problems/bi…
Method 1: Recursion
Time complexity: O(n)
Space complexity: O(h) at worst O(n)
Idea: The most basic recursion is res.add() between calls to left and right.
Code:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inOrder(root, res);
return res;
}
private void inOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return; } inOrder(root.left, res); res.add(root.val); inOrder(root.right, res); }}Copy the codeMethod 2: iteration, stack
Time complexity: O(n)
Space complexity: O(h) at worst O(n)
Idea: Use a stack to iterate over a Binary Tree Iterator. It’s like a lot of things… It does make sense, but at the end of the interview it becomes a template for memorization. But basically, what this means is, you go all the way to the left at the beginning, and you push all the Treenodes on the stack. Each time an element pops out, it must be traversed in middle order, so each time a node pops out, its next node needs to be added to the stack. The next node, in effect, is going to add its right subtree if it’s not empty, go to the right child, then go all the way to the left, and push all the Treenodes on the stack, so that the top of the stack is the next node.
Code:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> res = new ArrayList<>();
while(root ! =null) {
stack.push(root);
root = root.left;
}
while(! stack.isEmpty()) { TreeNode head = stack.pop(); res.add(head.val);if(head.right ! =null) {
head = head.right;
while(head ! =null) { stack.push(head); head = head.left; }}}returnres; }}Copy the codeMorris Traversal
Time complexity: O(n)
Space complexity: O(1)
Idea: Modify the preOrder slightly, res.add() in the bridge removal step.
Code:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
while(root ! =null) {
if (root.left == null) {
res.add(root.val);
root = root.right;
}
else {
TreeNode mostRight = root.left;
while(mostRight.right ! =null&& mostRight.right ! = root) { mostRight = mostRight.right; }if (mostRight.right == null) {
mostRight.right = root;
root = root.left;
}
else {
mostRight.right = null; res.add(root.val); root = root.right; }}}returnres; }}Copy the codeLeetCode 145 Binary Tree Postorder Traversal
Link: leetcode.com/problems/bi…
Method 1: Recursion
Time complexity: O(n)
Space complexity: O(h) at worst O(n)
Idea: The most basic recursion is res.add() after calling left and right.
Code:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postOrder(root, res);
return res;
}
private void postOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return; } postOrder(root.left, res); postOrder(root.right, res); res.add(root.val); }}Copy the codeMethod 2: iteration, stack
Time complexity: O(n)
Space complexity: O(h) at worst O(n)
Idea: I this problem is a reference flower sauce zxi.mytechroad.com/blog/tree/l… . It might not be easy for me to change my recursive code to use a stack, but what if I wanted to reverse the result backwards? We can change that to
private void postOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
postOrder(root.right, res);
postOrder(root.left, res);
}
Copy the codeOk, so how do I write this? This is very similar to the recursion of the previous iteration, except that the previous iteration is left and then right, and I’m going right and then left, so I’ll just change the solution of the previous iteration stack. When I change it to stack while, it’s going to be
while(! stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val);if(node.left ! =null) {
stack.push(node.left);
}
if(node.right ! =null) { stack.push(node.right); }}Copy the codeSo if you put the right in, the right will pop out first, and you’ll implement the pseudo code for the recursion above.
Finally, we reverse the result array, and we’re done.
Code:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(! stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val);if(node.left ! =null) {
stack.push(node.left);
}
if(node.right ! =null) {
stack.push(node.right);
}
}
Collections.reverse(res);
returnres; }}Copy the code