1. Preorder traversal of binary tree
Give you the root node of the binary tree, root, and return the preorder traversal of its node value.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return list;
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
2. Middle order traversal of binary tree
Force buckle OJ link
Given the root node of a binary tree, root, returns its middle order traversal.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return list;
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
return list;
}
}
3. Postorder traversal of binary tree
Force buckle OJ link
Given a binary tree, return its postorder traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) return list;
postorderTraversal(root.left);
postorderTraversal(root.right);
list.add(root.val);
return list;
}
}
4. Maximum depth of binary tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
5. Same tree
Force buckle OJ link
Give you the root nodes p and q of two binary trees and write a function to check whether the two trees are the same.
If two trees are structurally identical and the nodes have the same value, they are considered to be the same.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
}
if(isSameTree(p.left,q.left) && isSameTree(p.right,q.right)){
return true;
}
return false;
}
}
6. A subtree of another tree
Force buckle OJ link
Here are two binary trees, root and subRoot. Verify whether the root contains subtrees with the same structure and node values as the subRoot. If it exists, return true; Otherwise, false is returned.
A subtree of a binary tree tree includes a node of the tree and all descendants of this node. A tree can also be regarded as a subtree of its own.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
}
if(isSameTree(p.left,q.left) && isSameTree(p.right,q.right)){
return true;
}
return false;
}
public boolean isSubtree(TreeNode s, TreeNode t) {
if(s==null || t == null){
return false;
}
if(isSameTree( s, t)){
return true;
}
Boolean ret = isSubtree(s.left,t);
if(ret == true){
return true;
}
ret = isSubtree(s.right,t);
if(ret == true){
return true;
}
return false;
}
}
7. Symmetric binary tree
Force buckle OJ link
Given a binary tree, check whether it is mirror symmetric.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
if(leftTree == null && rightTree == null){
return true;
}
if(leftTree == null &&rightTree != null || leftTree != null && rightTree == null){
return false;
}
if(leftTree.val != rightTree.val) return false;
return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
}
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
if(isSymmetricChild(root.left,root.right)){
return true;
}
return false;
}
}
8. Balanced binary tree
Given a binary tree, judge whether it is a highly balanced binary tree.
In this question, a highly balanced binary tree is defined as:
The absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int getHeight(TreeNode root){
if(root == null){
return 0;
}
return Math.max(getHeight(root.left),getHeight(root.right)) +1;
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return Math.abs(getHeight(root.left)-getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
9. Sequence traversal of binary tree
To give you a binary tree, please return the node values obtained by traversing in sequence. (that is, access all nodes from left to right layer by layer).
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode cur = new TreeNode();
while(!queue.isEmpty()) {
List<Integer>list = new ArrayList<>();
int size = queue.size();
while(size >0){
cur = queue.poll();
list.add(cur.val);
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null ){
queue.add(cur.right);
}
size--;
}
ret.add(list);
}
return ret;
}
}
10. According to the string, build a binary tree (binary tree traversal)
Niuke link
Make a program to read a string of preorder traversal strings entered by the user, and establish a binary tree (stored in pointer mode) according to this string. For example, the following preorder traversal strings: ABC##DE#G##F### where "#" represents a space, and the space character represents an empty tree. After the binary tree is established, the binary tree is traversed in order, and the traversal result is output.
import java.util.*;
class BTNode{
public char val;
public BTNode left;//Reference of left subtree
public BTNode right;//Reference to right subtree
public BTNode(char val){
this.val = val;
}
}
public class Main{
public static int i = 0;
public static BTNode creatTree(String str){
if(str == null || str.length() < 0) return null;
BTNode root = null;
if(str.charAt(i) != '#'){
root = new BTNode(str.charAt(i));
i++;
root.left = creatTree(str);
root.right = creatTree(str);
}else{
i++;
}
return root;
}
public static void inOrderTraversal(BTNode root) {
if (root == null) return;
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
public static void main(String[]args){
Scanner scan = new Scanner(System.in);
String str = scan.nextLine();
BTNode root = creatTree(str);
inOrderTraversal(root);
}
}
11. Nearest common ancestor of two nodes
Given a binary tree, find the nearest common ancestor of two specified nodes in the tree.
Baidu Encyclopedia defines the nearest public ancestor as: "for two nodes p and q with root tree T, the nearest public ancestor is expressed as a node x, which satisfies that x is the ancestor of p and q, and the depth of X is as large as possible (a node can also be its own ancestor)."
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if( left != null && right != null){
return root;
}else if(left != null && right == null){
return left;
}else if(left == null && right != null){
return right;
}else{
return null;
}
}
}
12. Binary search tree and bidirectional linked list
Enter a binary search tree and convert the binary search tree into a sorted two-way linked list.
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode prev = null;
public void ConvertChild(TreeNode pCur) {
if( pCur == null) return;
ConvertChild(pCur.left);
pCur.left = prev;
if(prev != null){
prev.right = pCur;
}
prev = pCur;
ConvertChild(pCur.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) return null;
ConvertChild(pRootOfTree);
TreeNode head = pRootOfTree;
while(head.left != null){
head = head.left;
}
return head;
}
}
13. Constructing binary tree from preorder and inorder traversal sequences
Given the preorder and inorder of a tree. Construct a binary tree and return its root node.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int preIndex = 0;
public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
if(inbegin > inend) return null;
TreeNode root = new TreeNode(preorder[preIndex]);
//Find the position of the current root node in the array traversed in middle order
int index = findvalInorder(inorder,preorder[preIndex],inbegin,inend);
preIndex++;
root.left = buildTreeChild(preorder,inorder,inbegin,index-1);
root.right = buildTreeChild(preorder,inorder,index+1,inend);
return root;
}
public int findvalInorder(int[] inorder,int key,int inbegin,int inend){
for(int i = inbegin;i<=inend;i++){
if(inorder[i] == key){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null) return null;
if(preorder.length == 0 || inorder.length == 0) return null;
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
}
14. Constructing binary tree from middle order and post order traversal sequences
According to the middle order traversal and post order traversal of a tree, a binary tree is constructed.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int posIndex = 0;
public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
if(inbegin > inend) return null;
TreeNode root = new TreeNode(postorder[posIndex]);
//Find the position of the current root node in the array traversed in middle order
int index = findvalInorder(inorder,postorder[posIndex],inbegin,inend);
posIndex--;
root.right = buildTreeChild(postorder,inorder,index+1,inend);
root.left = buildTreeChild(postorder,inorder,inbegin,index-1);
return root;
}
public int findvalInorder(int[] inorder,int key,int inbegin,int inend){
for(int i = inbegin;i<=inend;i++){
if(inorder[i] == key){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder == null || inorder == null) return null;
if(postorder.length == 0 || inorder.length == 0) return null;
posIndex = postorder.length-1;
return buildTreeChild(postorder,inorder,0,inorder.length-1);
}
}
15. Create a string from a binary tree
Force buckle OJ link
You need to use preorder traversal to convert a binary tree into a string composed of parentheses and integers.
Empty nodes are represented by a pair of empty parentheses "()". And you need to omit all empty bracket pairs that do not affect the one-to-one mapping between the string and the original binary tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void tree2strChild(TreeNode t,StringBuilder sb ) {
if(t == null) return;
sb.append(t.val);
if(t.left == null){
if(t.right == null){
return;
}else{
sb.append("()");
}
}else{
sb.append("(");
tree2strChild(t.left,sb);
sb.append(")");
}
if(t.right == null){
return ;
}else{
sb.append("(");
tree2strChild(t.right,sb);
sb.append(")");
}
}
public String tree2str(TreeNode t) {
StringBuilder sb = new StringBuilder();
tree2strChild(t,sb);
return sb.toString();
}
}