辅助代码
import java.util.LinkedList;
import java.util.Queue;
public class TreeTools {
public static TreeNode CreateTree(String str){
String []arrays = str.split(",");
if(arrays == null || arrays.length == 0 || arrays[0] == null)
return null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode root = convert_str_to_TreeNode(arrays[0]);
queue.add(root);
int index = 1;
//层序构造树，借用队列的形式来构造树
while(!queue.isEmpty()){
TreeNode tmp = queue.poll();
if(tmp==null)
continue;
if(index==arrays.length)
break;
TreeNode left = convert_str_to_TreeNode(arrays[index]);
tmp.left = left;
index++;
queue.add(left);
if(index == arrays.length)
break;
TreeNode right = convert_str_to_TreeNode(arrays[index]);
tmp.right = right;
index++;
queue.add(right);
}
return root;
}
public static TreeNode convert_str_to_TreeNode(String str){
if(str.equals("#")){
return null;
}
else{
return new TreeNode(Integer.parseInt(str));
}
}
//比较巧妙的一种递归打印方式
private static void printNode(TreeNode tn, int indent) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indent; i++) {
sb.append("\t"); //需要添加多少个\t
}
sb.append(tn.val);
System.out.println(sb.toString());//换行
}
public static void printTree(TreeNode root, int indent) {
if (root == null) {
return;
}
// right
printTree(root.right, indent + 1);
// self
printNode(root, indent);
// left
printTree(root.left, indent + 1);
}
public static void printTree(TreeNode root) {
// right first
printTree(root, 0);
}
}
Same Tree
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: [1,2,3], [1,2,3]
Output: true
Example 2:
Input: [1,2], [1,null,2]
Output: false
Example 3:
Input: [1,2,1], [1,1,2]
Output: false
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;
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
res.addAll(inorderTraversal(root.left));
res.add(root.val);
res.addAll(inorderTraversal(root.right));
return res;
}
Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
public int numTrees(int n) {
//求能组成的二叉搜索树个数
int res = 0;
if(n<=1) return 1;
for(int i = 1;i<=n;i++){
res += numTrees(i-1)*numTrees(n-i); //numTrees(i-1)左子树排列个数 ; numTrees(n-i)右子树排列个数
}
return res;
}
Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
private List<TreeNode> generateTrees(int left,int right){
//生成从left，到right的所有搜索二叉树的可能
List<TreeNode> res = new ArrayList<TreeNode>();
if(left>right){
//终止条件
res.add(null);
return res;
}
for(int i = left;i<=right;i++){
List<TreeNode> leftTreeNodes = generateTrees(left,i-1); //以i作为根节点，左子树由[1,i-1]构成的list tree
List<TreeNode> rightTreeNodes = generateTrees(i+1,right);
for(int j = 0;j<leftTreeNodes.size();j++)
for(int k = 0;k<rightTreeNodes.size();k++){
TreeNode head = new TreeNode(i);
head.left = leftTreeNodes.get(j);
head.right = rightTreeNodes.get(k);
res.add(head);
}
}
return res;
}
public List<TreeNode> generateTrees(int n) {
//生成所有可能的二叉搜索树
//也是递归的方法
if(n<=0) return new ArrayList<TreeNode>(); //对n为0的情况特殊处理，对于n为0，上述递归条件会多加一个null
return generateTrees(1,n);
}
Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
else if(root.left == null && root.right == null && root.val == sum) return true;
else
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
public List<List<Integer>> pathSum(TreeNode root, int sum){
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null) return res;
List<Integer> path = new ArrayList<Integer>();
getpathSum(root,sum,path,res);
return res;
}
private void getpathSum(TreeNode root,int sum,List<Integer> path,List<List<Integer>> res){
if(root.val == sum && root.left == null && root.right == null){
path.add(sum);
res.add(new ArrayList<Integer>(path));
path.remove(path.size()-1);
}
else if(root.left==null&&root.right==null&&sum!=root.val){
return;
}
else{
path.add(root.val);
if(root.left!=null) getpathSum(root.left,sum-root.val,path,res);
if(root.right!=null) getpathSum(root.right,sum-root.val,path,res);
path.remove(path.size()-1);
}
}
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null) return res;
boolean leftToRight = true;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
//两个队列，一个是用来存放每层的结果(list)；另外一个是用来层序遍历树的
LinkedList<Integer> list = new LinkedList<Integer>();
int size = queue.size();
for(int i = 0;i<size;i++){
TreeNode tmp = queue.poll();
if(leftToRight){
list.addLast(tmp.val);
}
else{
list.addFirst(tmp.val);
}
if(tmp.left!=null){
queue.offer(tmp.left);
}
if(tmp.right!=null){
queue.offer(tmp.right);
}
}
res.add(list);
leftToRight = leftToRight?false:true;
}
return res;
Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<Integer>();
int size = queue.size();
for(int i = 0;i<size;i++){
TreeNode tmp = queue.poll();
list.add(tmp.val);
if(tmp.left!=null)
queue.add(tmp.left);
if(tmp.right!=null)
queue.add(tmp.right);
}
res.add(list);
}
return res;
}
Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
public int maxDepth(TreeNode root) {
if(root==null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null || inorder == null || preorder.length==0||inorder.length==0 || preorder.length!=inorder.length)
return null;
return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
private TreeNode buildTree(int[] preorder, int prestart,int preend,int[] inorder,int instart,int inend){
if(prestart>preend || instart>inend)
return null;
TreeNode root = new TreeNode(preorder[prestart]);
int rootindex = 0;
int len = 0;
for(int i = instart;i<=inend;i++){
if(inorder[i] == preorder[prestart]){
rootindex = i;
len = i-instart;
break;
}
}
root.left = buildTree(preorder,prestart+1,prestart+len,inorder,instart,rootindex-1);
root.right = buildTree(preorder,prestart+len+1,preend,inorder,rootindex+1,inend);
return root;
}
Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder==null || inorder == null || postorder.length==0||inorder.length==0 || postorder.length!=inorder.length)
return null;
return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
private TreeNode buildTree(int[] inorder,int instart,int inend,int[] postorder, int poststart,int postend){
if(poststart>postend || instart>inend)
return null;
TreeNode root = new TreeNode(postorder[postend]);
int rootindex = 0;
int len = 0;
for(int i = instart;i<=inend;i++){
if(inorder[i] == postorder[postend]){
rootindex = i;
len = i-instart;
break;
}
}
root.left = buildTree(inorder,instart,rootindex-1,postorder,poststart,poststart+len-1);
root.right = buildTree(inorder,rootindex+1,inend,postorder,poststart+len,postend-1);
return root;
}
Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
public int minDepth(TreeNode root) {
if(root==null) return 0;
else if(root.left==null&&root.right==null) return 1;
else{
//要注意如果有个节点只有一边孩子时，不能返回0，要返回另外一半边的depth。
int left = minDepth(root.left);
int right = minDepth(root.right);
if(left==0||right==0){
return left==0?right+1:left+1;
}
return Math.min(left,right)+1;
}
}
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
public void flatten(TreeNode root) {
if(root == null) return;
flatten(root.left);
flatten(root.right);
TreeNode tmp = null;
if(root.right!=null){
tmp = root.right;
}
root.right = root.left;
root.left = null;
while(root.right!=null) {
root = root.right;
}
root.right = tmp;
}
Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
public void connect(TreeLinkNode root) {
//针对完全二叉树的情况,递归方法
//从上往下递归
if(root == null) return;
if(root.left!=null) root.left.next = root.right;
if(root.right!=null) root.right.next = root.next==null?null:root.next.left;
connect(root.left);
connect(root.right);
}
public void connect(TreeLinkNode root){
if(root == null) return;
LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0;i<size;i++){
TreeLinkNode tmp = queue.poll();
//tmp.next = (queue.isEmpty())?null:queue.peek(); //fail 为什么
tmp.next = (i==size-1)?null:queue.peek();
if(tmp.left!=null) queue.add(tmp.left);
if(tmp.right!=null) queue.add(tmp.right);
}
}
}
Populating Next Right Pointers in Each Node II
同上一个问题非递归解法
