1. Preorder traversal of binary tree
The title comes from LeetCode problem 144: antecedent traversal of binary trees.
Topic describes
Given a binary tree, return its prior traversal.
title
Use the ** Stack (Stack)** idea to deal with the problem.
The order of the preceding traversal is root-left-right, and the specific algorithm is as follows:
- Push the root node onto the stack
- The loop checks whether the stack is empty. If not, it retrieves the top element of the stack and saves its value
- See if the right child exists and push it onto the stack if it does
- Look at the left child and push it on the stack if it exists.
Animation description
Code implementation
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new LinkedList<>();
if(root == null) {return list;
}
// The first step is to push the root node onto the stack
stack.push(root);
// When the stack is not empty, the element out of the stack is inserted at the end of the list.
while(! stack.isEmpty()){ root = stack.pop(); list.add(root.val);if(root.right ! =null) stack.push(root.right);
if(root.left ! =null) stack.push(root.left);
}
returnlist; }}Copy the code2. Middle order traversal of binary tree
The title comes from LeetCode problem no. 94: middle order traversal of binary trees.
Topic describes
Given a binary tree, return its middle-order traversal.
title
Use the ** Stack (Stack)** idea to deal with the problem.
The order of middle-order traversal is left-root-right, and the specific algorithm is as follows:
- Starting with the root node, the root node is pushed onto the stack first
- Then all of its left children are pushed onto the stack, the top node is removed, and the node value is saved
- The current pointer is then moved to its right child, and if there is a right child, all its left children can be pushed on the next loop
Animation description
Code implementation
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur ! =null| |! stack.isEmpty()) {if(cur ! =null) {
stack.push(cur);
cur = cur.left;
} else{ cur = stack.pop(); list.add(cur.val); cur = cur.right; }}returnlist; }}Copy the code3. Back-order traversal of binary trees
The title comes from LeetCode problem no. 145: backward traversal of binary trees.
Topic describes
Given a binary tree, return its backward traversal.
title
Use the ** Stack (Stack)** idea to deal with the problem.
The order of post-order traversal is left-right-root, and the specific algorithm is as follows:
- First push the root node onto the stack, and then define a secondary node head
- The condition of the while loop is that the stack is not empty
- In the loop, we first pull out the top node t
- If the top of the stack has no left and right children, or its left child is head, or its right child is head. We add the value of the top of the stack to the result RES, move the top element off the stack, and then point the head to the top element
- Otherwise, if the right child is not empty, add it to the stack
- And if the left child isn’t empty, we add it to the stack
Animation description
Code implementation
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(! stack.isEmpty()){ TreeNode node = stack.pop();if(node.left ! =null) stack.push(node.left);// Instead of traditional sequential traversal, the left node is pushed first
if(node.right ! =null) stack.push(node.right);// push the right node onto the stack
res.add(0,node.val); // Add node values in reverse order
}
returnres; }}Copy the code4. Sequence traversal of binary tree
The title comes from LeetCode problem no. 102: sequential traversal of binary trees.
Topic describes
Given a binary tree, return the value of the nodes traversed hierarchically. (That is, layer by layer, all nodes are accessed from left to right).
For example, given a binary tree: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Copy the codeReturns the result of its hierarchical traversal:
[[3], [9,20], [15,7]Copy the codetitle
This problem requires queues.
- Create a queue
- Put the root node in first, and then look for the left and right children of the root node
- Remove the root node, and the elements in the queue are all nodes in the next layer
- Iterate through it with a for loop, storing the result in a one-dimensional vector
- And then I’m going to take the one-dimensional vector and put it in the two-dimensional vector
- In this way, sequence traversal can be completed
Animation description
Code implementation
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null)
return new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(! queue.isEmpty()){int count = queue.size();
List<Integer> list = new ArrayList<Integer>();
while(count > 0){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left ! =null)
queue.add(node.left);
if(node.right ! =null)
queue.add(node.right);
count--;
}
res.add(list);
}
return res;
}
Copy the code5. Balanced binary trees
The title comes from LeetCode problem 110: Balanced binary trees.
Topic describes
Given a binary tree, determine whether it is a highly balanced binary tree.
title
Each node of the binary tree is traversed by the way of sequential traversal.
The left and right subtrees of a node have been traversed before reaching it, so as long as the depth of each node is recorded when traversing it (the depth of a node is equal to the length of its path to the leaf node), we can judge whether each node is balanced while traversing it.
Code implementation
class Solution {
private boolean isBalanced = true;
public boolean isBalanced(TreeNode root) {
getDepth(root);
return isBalanced;
}
public int getDepth(TreeNode root) {
if (root == null)
return 0;
int left = getDepth(root.left);
int right = getDepth(root.right);
if (Math.abs(left - right) > 1) {
isBalanced = false;
}
return right > left ? right + 1 : left + 1; }}Copy the code6. Symmetric binary trees
The title comes from LeetCode problem no. 101: symmetric binary trees.
Topic describes
Given a binary tree, check whether it is mirror – symmetric.
For example, binary trees [1,2,2,3,4,4,3] are symmetric.
1
/ \
2 2
/ \ / \
3 4 4 3
Copy the codetitle
Recursion is simple: a tree that is symmetric is equivalent to its left and right subtrees. The problem is to determine whether the two trees are symmetric or not.
Code implementation
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
// Change the question to whether the two trees are symmetric
return isSym(root.left, root.right);
}
// Check whether the two trees with roots r1 and R2 are symmetric
public boolean isSym(TreeNode r1, TreeNode r2){
if(r1 == null && r2 == null) return true;
if(r1 == null || r2 == null) return false;
// These two trees are symmetric:
//1. The two root nodes are equal. 2. The left subtree of tree 1 and the right subtree of tree 2, the left subtree of tree 2 and the right subtree of tree 1 have to be symmetric
returnr1.val == r2.val && isSym(r1.left, r2.right) && isSym(r1.right, r2.left); }}Copy the code7. Rebuild the binary tree
Offer: Rebuild binary tree.
Topic describes
The binary tree is reconstructed according to the results of pre-order traversal and middle-order traversal. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers.
Preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Copy the codetitle
The first value of the pre-order traversal is the value of the root node, which is used to divide the middle-order traversal result into two parts. The left part is the result of the middle-order traversal in the left subtree of the tree, and the right part is the result of the middle-order traversal in the right subtree of the tree.
Animation description
Code implementation
// The index corresponding to each value of the sequential traversal group in the cache
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
for (int i = 0; i < in.length; i++)
indexForInOrders.put(in[i], i);
return reConstructBinaryTree(pre, 0, pre.length - 1.0);
}
private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
if (preL > preR)
return null;
TreeNode root = new TreeNode(pre[preL]);
int inIndex = indexForInOrders.get(root.val);
int leftTreeSize = inIndex - inL;
root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
return root;
}
Copy the code