Article directory
-
- Hierarchical traversal template
- Hierarchical traversal hierarchical storage template
- Hierarchical traversal bottom-up
- Zigzag level traversal
- Level traversal of N-ary tree
- Find the maximum value at each level of a binary tree
- Find the average value of each level of a binary tree
- Right view of binary tree
- The value in the lower left corner of the binary tree
- Binary tree preorder traversal recursive writing
- Recursive writing of in-order traversal of a binary tree
- Binary tree post-order traversal recursive writing
- Iterative writing method for preorder traversal of binary tree
- Iterative writing method for in-order traversal of a binary tree
- Iterative writing method for post-order traversal of a binary tree
- Determine whether two binary trees are the same
- Determine whether a binary tree is symmetrical
- Merge binary trees
- All paths in the binary tree
- path sum
- Reverse a binary tree
- The maximum depth of a binary tree
- height of binary tree
- Judgment Balance Tree
- minimum depth
- Maximum depth of N-ary tree
- most recent common ancestor
Hierarchical traversal template
Understand the process of using queues to traverse binary tree levels
public List<Integer> levelOrder(TreeNode root){<!-- -->
List<Integer> res = new ArrayList<>();
if(root==null){<!-- -->
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()){<!-- -->
TreeNode node = queue.poll();
res.add(node.val);
if(node.left!=null){<!-- -->
queue.offer(node.left);
}
if(node.right!=null){<!-- -->
queue.offer(node.right);
}
}
return res;
}
Hierarchical traversal hierarchical storage template
Hierarchical traversal and hierarchical storage are the basis for solving the following problems
public List<List<Integer>> levelOrder(TreeNode root) {<!-- -->
List<List<Integer>> res = new ArrayList<>();
if(root==null){<!-- -->
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
List<Integer> list = new ArrayList<>();
int size = queue.size();
for(int i=0;i<size;i + + ){<!-- -->
TreeNode node = queue.poll();
list.add(node.val);
if(node.left!=null){<!-- -->
queue.offer(node.left);
}
if(node.right!=null){<!-- -->
queue.offer(node.right);
}
}
res.add(list);
}
return res;
}
Hierarchical traversal bottom-up
Traverse the template according to the levels, and after traversing the data of each layer, store the current layer at the head of the list
public List<List<Integer>> levelOrderBottom(TreeNode root) {<!-- -->
List<List<Integer>> res = new LinkedList<List<Integer>>();
if(root==null){<!-- -->
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(queue.size()>0){<!-- -->
int size = queue.size();
List<Integer> treeList = new ArrayList<Integer>();
for(int i=0;i<size;i + + ){<!-- -->
TreeNode treeNode = queue.poll();
treeList.add(treeNode.val);
if(treeNode.left!=null){<!-- -->
queue.add(treeNode.left);
}
if(treeNode.right!=null){<!-- -->
queue.add(treeNode.right);
}
}
res.add(0,treeList);
}
return res;
}
Zigzag level traversal
Set a traversal flag to determine whether the traversal is from left to right. Use a double-ended queue to determine the order of entry according to the order of traversal requirements
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {<!-- -->
List<List<Integer>> res = new ArrayList<>();
if(root==null){<!-- -->
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
boolean fromLeftToRight = true;
while (!queue.isEmpty()) {<!-- -->
int size = queue.size();
Deque<Integer> treeList = new LinkedList<Integer>();
for(int i = 0; i < size; i + + ){<!-- -->
TreeNode treeNode = queue.poll();
if(fromLeftToRight){<!-- -->
treeList.offerLast(treeNode.val);
}else{<!-- -->
treeList.offerFirst(treeNode.val);
}
if(treeNode.left!=null){<!-- -->
queue.offer(treeNode.left);
}
if(treeNode.right!=null){<!-- -->
queue.offer(treeNode.right);
}
}
fromLeftToRight = !fromLeftToRight;
res.add(new LinkedList<>(treeList));
}
return res;
}
Level traversal of N-ary tree
It is not much different from the hierarchical traversal of a binary tree. The difference is that the hierarchical traversal of a binary tree is that after the node is dequeued, the left and right children are enqueued. The hierarchical traversal of the N-ary tree is that after the node is dequeued, all the child nodes are enqueued.
public List<List<Integer>> levelOrder(Node root) {<!-- -->
List<List<Integer>> res = new ArrayList<>();
if(root==null){<!-- -->
return res;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
int size = queue.size();
List<Integer> nodeList = new ArrayList<>();
for(int i=0;i<size;i + + ){<!-- -->
Node node = queue.poll();
nodeList.add(node.val);
for(Node child:node.children){<!-- -->
queue.offer(child);
}
}
res.add(nodeList);
}
return res;
}
Find the maximum value of each level of the binary tree
When traversing, set a variable for each layer to store the maximum value, and continuously update the variable during the convenience process, and finally obtain the maximum value for each layer
public List<Integer> largestValues(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<>();
if(root==null){<!-- -->
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
int max = Integer.MIN_VALUE;
int size = queue.size();
for(int i=0;i<size;i + + ){<!-- -->
TreeNode node = queue.poll();
int val = node.val;
max = max>val?max:val;
if(node.left!=null){<!-- -->
queue.offer(node.left);
}
if(node.right!=null){<!-- -->
queue.offer(node.right);
}
}
res.add(max);
}
return res;
}
Find the average value of each level of the binary tree
The same method as finding the maximum value of each layer
public List<Double> averageOfLevels(TreeNode root) {<!-- -->
List<Double> res = new ArrayList<>();
if(root==null){<!-- -->
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
double sum = 0;;
int size = queue.size();
for(int i=0;i<size;i + + ){<!-- -->
TreeNode node = queue.poll();
sum + = node.val;
if(node.left!=null){<!-- -->
queue.offer(node.left);
}
if(node.right!=null){<!-- -->
queue.offer(node.right);
}
}
res.add(sum/size);
}
return res;
}
Right view of a binary tree
When facilitating each layer, save the number of nodes currently traversed equal to queue size-1, and finally you can get the right view of the binary tree
public List<Integer> rightSideView(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<>();
if(root==null){<!-- -->
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
double sum = 0;;
int size = queue.size();
for(int i=0;i<size;i + + ){<!-- -->
TreeNode node = queue.poll();
if(i==size-1){<!-- -->
res.add(node.val);
}
if(node.left!=null){<!-- -->
queue.offer(node.left);
}
if(node.right!=null){<!-- -->
queue.offer(node.right);
}
}
}
return res;
}
The value of the lower left corner of the binary tree
When traversing, when a node is dequeued, the right child is enqueued first, and then the left child is enqueued, so that the last node visited is the value in the lower left corner of the binary tree
public int findBottomLeftValue(TreeNode root) {<!-- -->
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int res = 0;
while(!queue.isEmpty()){<!-- -->
TreeNode node = queue.poll();
res = node.val;
if(node.right!=null){<!-- -->
queue.offer(node.right);
}
if(node.left!=null){<!-- -->
queue.offer(node.left);
}
}
return res;
}
Binary tree pre-order traversal recursive writing
public List<Integer> preorderTraversal(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<>();
preorderTraversal(root,res);
return res;
}
public void preorderTraversal(TreeNode root,List<Integer> res){<!-- -->
if(root==null){<!-- -->
return;
}
res.add(root.val);
preorderTraversal(root.left,res);
preorderTraversal(root.right,res);
}
How to write recursive in-order traversal of a binary tree
public List<Integer> inorderTraversal(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<>();
inorderTraversal(root,res);
return res;
}
public void inorderTraversal(TreeNode root,List<Integer> res){<!-- -->
if(root==null){<!-- -->
return;
}
inorderTraversal(root.left,res);
res.add(root.val);
inorderTraversal(root.right,res);
}
Binary tree post-order traversal recursive writing
public List<Integer> postorderTraversal(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<Integer>();
postOrderTraversal(root,res);
return res;
}
public void postOrderTraversal(TreeNode root,List<Integer> res){<!-- -->
if(root==null){<!-- -->
return;
}
postOrderTraversal(root.left,res);
postOrderTraversal(root.right,res);
res.add(root.val);
}
The iterative writing method of preorder traversal of a binary tree
Use the stack to perform pre-order traversal of the binary tree from the root to the left
public List<Integer> preorderTraversal(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while(root!=null || !stack.isEmpty()){<!-- -->
while(root!=null){<!-- -->
res.add(root.val);
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return res;
}
Iterative writing method for in-order traversal of a binary tree
Use the stack to perform in-order traversal of the binary tree in a left-root-right manner
public List<Integer> inorderTraversal(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while(root!=null || !stack.isEmpty()){<!-- -->
while(root!=null){<!-- -->
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
The iterative writing method of post-order traversal of a binary tree
Use the stack to traverse the binary tree in a root-right-left manner, and then reverse the result, which is the subsequent traversal of the binary tree
public List<Integer> postorderTraversal(TreeNode root) {<!-- -->
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while(root!=null || !stack.isEmpty()){<!-- -->
while(root!=null){<!-- -->
res.add(root.val);
stack.push(root);
root = root.right;
}
root = stack.pop();
root = root.left;
}
Collections.reverse(res);
return res;
}
Determine whether two binary trees are the same
Compare two binary trees to see if they are empty at the same time. If they are empty at the same time, they are the same. If they are not empty at the same time, they are not the same. If they are not empty at the same time, compare whether the root node and the left and right subtrees are the same.
public boolean isSameTree(TreeNode p, TreeNode q) {<!-- -->
if(p==null & amp; & amp;q==null){<!-- -->
return true;
}
if(p==null||q==null){<!-- -->
return false;
}
if(p.val!=q.val){<!-- -->
return false;
}
return isSameTree(p.left,q.left) & amp; & amp;isSameTree(p.right,q.right);
}
Determine whether a binary tree is symmetrical
Determine whether the binary tree is empty. If it is empty, it is symmetrical. If it is not empty, compare whether the left and right subtrees are symmetrical
public boolean isSymmetric(TreeNode root) {<!-- -->
if(root==null){<!-- -->
return true;
}
return isSymmetric(root.left,root.right);
}
public boolean isSymmetric(TreeNode p,TreeNode q){<!-- -->
if(p==null & amp; & amp;q==null){<!-- -->
return true;
}
if(p==null||q==null){<!-- -->
return false;
}
if(p.val!=q.val){<!-- -->
return false;
}
return isSymmetric(p.left,q.right) & amp; & amp;isSymmetric(p.right,q.left);
}
Merge binary trees
Determine whether at least one binary tree is empty. If it is empty, it will be returned directly. If both binary trees are not empty at the same time, merge the root node first, and then merge the left and right subtrees
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {<!-- -->
if(root1==null || root2==null){<!-- -->
return root1==null?root2:root1;
}
TreeNode merged = new TreeNode(root1.val + root2.val);
merged.left = mergeTrees(root1.left,root2.left);
merged.right = mergeTrees(root1.right,root2.right);
return merged;
}
All paths in the binary tree
Define a variable to record the current path, and define a list to store all paths. When the left and right subtrees of the current node are empty, it indicates that the path has reached the end point, and the path is added to the path list. Otherwise, the current path is added to the node. Continue to recursively search the left and right subtrees of the current node
public List<String> binaryTreePaths(TreeNode root) {<!-- -->
List<String> res = new ArrayList<>();
searchPath(root,"",res);
return res;
}
public void searchPath(TreeNode root, String path, List<String> res){<!-- -->
if(root==null){<!-- -->
return;
}
if(root.left==null & amp; & amp;root.right==null){<!-- -->
path = path + root.val;
res.add(path);
return;
}
searchPath(root.left,path + root.val + "->",res);
searchPath(root.right,path + root.val + "->",res);
}
Sum of paths
Each time a node is traversed, the target sum is subtracted from the node value. When the left and right subtrees of the currently traversed node are empty, determine whether the current node value is equal to the target sum
public boolean hasPathSum(TreeNode root, int targetSum) {<!-- -->
if(root==null){<!-- -->
return false;
}
targetSum-=root.val;
if(root.left==null & amp; & amp;root.right==null & amp; & amp;targetSum==0){<!-- -->
return true;
}
return hasPathSum(root.left,targetSum) || hasPathSum(root.right,targetSum);
}
Reverse a binary tree
If the binary tree is empty, return directly. Otherwise, exchange the left and right child nodes, and recursively exchange the left and right subtrees
public TreeNode invertTree(TreeNode root) {<!-- -->
if(root==null){<!-- -->
return root;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
The maximum depth of a binary tree
The maximum depth of a binary tree is equal to the maximum depth of the left and right subtrees plus one
public int maxDepth(TreeNode root) {<!-- -->
if(root==null){<!-- -->
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right) + 1;
}
public int maxDepth(TreeNode root) {<!-- -->
if(root==null){<!-- -->
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int maxDepth = 0;
while(!queue.isEmpty()){<!-- -->
maxDepth + + ;
int size = queue.size();
for(int i=0;i<size;i + + ){<!-- -->
root = queue.poll();
if(root.left!=null){<!-- -->
queue.offer(root.left);
}
if(root.right!=null){<!-- -->
queue.offer(root.right);
}
}
}
return maxDepth;
}
The height of a binary tree
The maximum height of a binary tree is equal to the maximum height of the left and right subtrees plus one.
public int height(TreeNode root){<!-- -->
if(root==null){<!-- -->
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight,rightHeight) + 1;
}
Judgment balanced tree
Calculate the height of the left and right subtrees and determine whether the height difference is less than 1
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
boolean rootBalanced = Math.abs(height(root.left)-height(root.right))<=1;
boolean leftBalanced = isBalanced(root.left);
boolean rightBalanced = isBalanced(root.right);
return rootBalanced & amp; & amp;leftBalanced & amp; & amp;rightBalanced;
}
public int height(TreeNode root){<!-- -->
if(root==null){<!-- -->
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight,rightHeight) + 1;
}
public boolean isBalanced(TreeNode root) {<!-- -->
return height(root)>=0;
}
public int height(TreeNode root){<!-- -->
if(root==null){<!-- -->
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if(leftHeight==-1 || rightHeight== -1 || Math.abs(leftHeight-rightHeight)>1){<!-- -->
return -1;
}else{<!-- -->
return Math.max(leftHeight,rightHeight) + 1;
}
}
Minimum depth
Find the minimum depth of the left and right subtrees that are not empty
public int minDepth(TreeNode root) {<!-- -->
if(root==null){<!-- -->
return 0;
}
if(root.left==null & amp; & amp;root.right==null){<!-- -->
return 1;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if(root.left==null || root.right==null){<!-- -->
return leftDepth + rightDepth + 1;
}
return Math.min(leftDepth,rightDepth) + 1;
}
public int minDepth(TreeNode root) {<!-- -->
if(root==null){<!-- -->
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int minDepth = 0;
while(!queue.isEmpty()){<!-- -->
minDepth + + ;
int size = queue.size();
for(int i=0;i<size;i + + ){<!-- -->
root = queue.poll();
if(root.left==null & amp; & amp;root.right==null){<!-- -->
return minDepth;
}
if(root.left!=null){<!-- -->
queue.offer(root.left);
}
if(root.right!=null){<!-- -->
queue.offer(root.right);
}
}
}
return minDepth;
}
The maximum depth of N-ary tree
The same principle as the maximum depth of a binary tree
public int maxDepth(Node root) {<!-- -->
if(root==null){<!-- -->
return 0;
}
int maxDepth = 0;
for(Node node:root.children){<!-- -->
int depth = maxDepth(node);
if(depth>maxDepth){<!-- -->
maxDepth = depth;
}
}
return maxDepth + 1;
}
Latest common ancestor
Look for two nodes in the left and right subtrees. If the two nodes are on different sides, the root is the nearest common ancestor. On the same side, determine whether the root node of the current side is equal to one of the two nodes. If equal, return , otherwise continue searching in the left and right subtrees on that side
private TreeNode res = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {<!-- -->
dfs(root,p,q);
return res;
}
public boolean dfs(TreeNode root, TreeNode p,TreeNode q){<!-- -->
if(root==null){<!-- -->
return false;
}
boolean left = dfs(root.left,p,q);
boolean right = dfs(root.right,p,q);
if(left & amp; & amp;right){<!-- -->
res = root;
}
if(root == p || root ==q){<!-- -->
res = root;
}
return left || right || root==p || root==q;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {<!-- -->
if(root==p || root==q || root==null){<!-- -->
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left==null & amp; & amp;right==null){<!-- -->
return null;
}
if(left==null){<!-- -->
return right;
}
if(right==null){<!-- -->
return left;
}
return root;
}