从简单到难开始写起

树部分

104. Maximum Depth of Binary Tree（深度优先）

Easy

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.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / 
  9  20
    /  
   15   7

return its depth = 3.


贴代码

这是递归版本的：

 // // Definition for a binary tree node.
 //  struct TreeNode {
 //      int val;
 //      TreeNode *left;
 //      TreeNode *right;
 //      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 //  };

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int maxdepth=0;
        DFS(maxdepth,root,maxdepth);
        return maxdepth;
    }
    void DFS(int maxtemp,TreeNode* root,int& maxdepth){
        if(root==NULL) return;
        if(maxtemp+1>maxdepth) maxdepth=maxtemp+1;
        DFS(maxtemp+1,root->left,maxdepth);    
        DFS(maxtemp+1,root->right,maxdepth);
    }    
};

这是非递归版本的，使用了栈
 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s1, s2;
        if (p) s1.push(p);
        if (q) s2.push(q);
        while (!s1.empty() && !s2.empty()) {
            TreeNode *t1 = s1.top(); s1.pop();
            TreeNode *t2 = s2.top(); s2.pop();
            if (t1->val != t2->val) return false;
            if (t1->left) s1.push(t1->left);//左或者右优先都可以，因为先序遍历的定义是先访问根节点，然后访问
// 叶子节点，这里应该是先访问了右孩子
            if (t2->left) s2.push(t2->left);
            if (s1.size() != s2.size()) return false;
            if (t1->right) s1.push(t1->right);
            if (t2->right) s2.push(t2->right);
            if (s1.size() != s2.size()) return false;
        }
        return s1.size() == s2.size();
    }
};

结果是非递归版本的比较快

108. Convert Sorted Array to Binary Search Tree（深度优先）

Easy

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / 
   -3   9
   /   /
 -10  5

题目：给定一个升序排列的数组，转换成高度平衡的二叉排序树（Binary Search Tree）
我们先来看二叉排序树的定义（维基百科）：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3. 任意节点的左、右子树也分别为二叉查找树；

4. 没有键值相等的节点。

也就是

右子树>根节点>左节点

这种排序树的好处是查找和插入的时间复杂度比较低

我们再来看一下平衡树的特点

平衡树的任一节点的左右子树的高度差不超过1

我们再来看看这棵树
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / 
   -3   9
   /   /
 -10  5

贴代码（注意这个是Java，大同小异）

其实就是将数组不断一分为二，然后每次总取中间的值作为根节点，递归建树，而且建出来就是平衡的，也就是说如果遇到建立二叉平衡树，将所有的数据先进行排序是一个必要的过程
 

//  Definition for a binary tree node.
//  public class TreeNode {
//     int val;
//      TreeNode left;
//      TreeNode right;
//     TreeNode(int x) { val = x; }
//  }

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length==0||nums==null) {
			return null;//错误排除
		   }
		   return CreatTree(nums, 0, nums.length-1);            
    }
     public TreeNode  CreatTree(int[] nums,int index_start,int index_end) {
			 if (index_start>index_end) {
				 return null;
			}
			 int mid=(index_end+index_start)/2;
			 TreeNode myNode=new TreeNode(nums[mid]);
			 myNode.left=CreatTree(nums, index_start, mid-1);
			 myNode.right=CreatTree(nums, mid+1, index_end);
			 return myNode;
		 }
}

109. Convert Sorted List to Binary Search Tree（深度优先）

Medium

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / 
   -3   9
   /   /
 -10  5

似曾相识，但是这道题是给定链表，不是给定数组

数组的好处是查找时间复杂度低，空间利用率有时不充分以及不灵活这些缺点，相对的链表空间利用率高，比较灵活，不要求数据存储在一块连续的空间上，相反链表的缺点就是查找时间复杂度比较高

那就遍历一遍链表然后生成一个数组呗，那是你期末上机A题的时候机灵的做法，但是其实只需要使用一点小技巧即可实现建树
贴代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    ListNode SignNode;
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode node = head;
        int count = 0;
        while (node != null) {
            node = node.next;
            count++;
        }
        SignNode= head;
        return CreateTree(0, count - 1);
    }
    
    private TreeNode CreateTree(int index_start, int index_end) {
        if (index_start> index_end) 
            return null;
        //依旧是二分
        int mid=(index_start+index_end)/2; 
        TreeNode left = CreateTree(index_start, mid - 1);//左节点不断递归创建直到下标的起始值大于下标的结束值时结束递归
        TreeNode root = new TreeNode(SignNode.val);//最左的节点一开始使用了列表的第一个节点
        SignNode= SignNode.next;//中间节点使用了次左边的节点
        TreeNode right = CreateTree(mid + 1, index_end);
        root.left = left;
        root.right = right;
        return root;
    }
}

102. Binary Tree Level Order Traversal（深度优先搜索or广度优先搜索版本）

Medium

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / 
  9  20
    /  
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

题目：给定一个二叉树，写出对应的层序遍历

Java是一把利器，这道题用到ArrayList,先来复习一下
      

        ArrayList<Object> arrayList = new ArrayList<>();
        //1.大小
        arrayList.size();
        //2.添加
        arrayList.add(new Object());
        //3.指定位置添加
        arrayList.add(0, new Object());
        //4.判断对象是否在容器内(引用判断) 返回 boolean 值
        arrayList.contains(new Object());
        //5.获取指定位置的对象(范围内)
        arrayList.get(index);
        //6.获取对象位置(有相同引用的对象 返回最前的下标)
        arrayList.indexOf(new Object());
        //7.删除指定下标的对象
        arrayList.remove(index);
        //8.删除指定对象(有相同引用删除 最前面的)
        arrayList.remove(new Object());
        //9.删除全部
        arrayList.clear();
        arrayList.removeAll(arrayList);
        //10.替换 指定下标的对象
        arrayList.set(index, new Object());
        //11.转换为指定泛型的数组
        Object []object = arrayList.toArray(new Object []{});
        //12.添加另一个容器的所有对象
        arrayList.addAll(new ArrayList());//添加到最后
        arrayList.addAll(index,new ArrayList());//在指定位置添加

贴代码
先是深度优先搜索版本

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
	        List<List<Integer>> result = new ArrayList<>();
	        Leveltraverse(root, 1, result);
	        return result;
	    }
	    void Leveltraverse(TreeNode root, int level,
	                  List<List<Integer>> result) {
	        if (root == null) return;
	 
	        if (level > result.size())//新建一层就要新建一个空的数组
	            result.add(new ArrayList<>());
	 
	        result.get(level-1).add(root.val);
	        Leveltraverse(root.left, level+1, result);//实际上是深度优先
	        Leveltraverse(root.right, level+1, result);
	    }
}

其次是广度优先搜索版本（我们需要搭配队列来使用，每次需要判断队列是否为空）

这里有一点需要注意的是    Queue或者List都是Java的接口，不能直接用来实例化对象
需要使用它们的子类实例化之后赋值给父类（也就是上转型对象）

也就是不能直接  Queue<某某> mylist=new Queue<某某>()；

而且注意到队列类LinkedList  实现了Queue接口
 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   public List<List<Integer>> levelOrder(TreeNode root) {
	        List<List<Integer>> result =new ArrayList<>();
	        if (root==null) {
	        	return result;
			}
	        Queue<TreeNode> queue=new LinkedList<TreeNode>();
	        queue.add(root);
	        while(queue.isEmpty()==false) {
	        	//每次判断队列是不是空
	        	int size=queue.size();//注意这一句如果不写就是一个坑，进入下面for循环的时候size元素会随着add操作而增加
	        	//但是每次for循环只需要遍历完一层节点即可
	        	List <Integer> oneIntegers=new LinkedList<>();
	        	for (int i = 0; i < size; i++) {
	        		TreeNode topNode=queue.poll();//得到第一个元素并且将其弹出
	        		oneIntegers.add(topNode.val);
	        		if (topNode.left!=null) {
	        			queue.add(topNode.left);						
	        			
					}
	        		if (topNode.right!=null) {
	        			queue.add(topNode.right);						
	        		}
				}
	        	result.add(oneIntegers);
	        }
	        return result;
	     
	    }
}

到这里我们稍微做一下总结，如果是递归写法，那大致框架是一个全局函数加上一个递归调用的函数；如果是非递归写法，大致框架是一个while循环，用上队列（FIFO）或者堆栈（LIFO），具体结合其性质分情况使用

112. Path Sum（深度优先遍历）

Easy

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,

      5
     / 
    4   8
   /   / 
  11  13  4
 /        
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

样例
[5,4,8,11,null,13,4,7,2,null,null,null,1]（这是一棵已经有的二叉树）
22（sum）

题目：从根节点到叶子节点，如果有一条路径的总和等于给定的sum值，则返回true,反之false
 

一开始的想法是一路做加法，然后判断叶子节点的值是不是等于sum，最后看到一个做减法的，觉得比较简洁

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
      if(root==null)
    		return false;
    	if(root.right==null&&root.left==null&&root.val==sum)
    		return true;
    	return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);	 	  
    }
}

这是Java中的stack
http://www.runoob.com/java/java-stack-class.html