aquawj

//traverse
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        traverse(result, root);
        return result;
    }
    public void traverse(List<Integer> result, TreeNode root){  //result在traverse函数的参数中
        if(root == null) return;
        traverse(result, root.left);
        result.add(root.val);

aquawj

// 时间复杂度： O(n)
// divide & conquer （好理解）
public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if(root == null) return list;
        if(root.left == null && root.right == null){  //叶子节点也判断
            list.add(String.valueOf(root.val));
        }
        List<String> left = binaryTreePaths(root.left);
        List<String> right = binaryTreePaths(root.right);

aquawj

// 时间复杂度： O(n)
// divide & conquer （好理解）
public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if(root == null) return list;
        if(root.left == null && root.right == null){  //叶子节点也判断
            list.add(String.valueOf(root.val));
        }
        List<String> left = binaryTreePaths(root.left);
        List<String> right = binaryTreePaths(root.right);

aquawj

// 题目：The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
// diameter设为全局变量
// 辅助函数： 计算每个点的depth，随时更新diameter值
class Solution {
    int diameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        depth(root);

aquawj

/*Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.
*/
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

aquawj

Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root
  For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.
最大路径和。不一定经过root，不一定经过叶子。要考虑可能有的节点value为负数。和之前diameter题目的区别在，不是找最长的路径，而是某路径sum最大。

aquawj

//1. 两个节点p，q都存在
//时间：O(n) 总的节点数
//空间：O(h) 高度
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){ //3种情况
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

aquawj

//BST中的LAC： 比较val大小即可
// easy
//1. recursion
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val > q.val){ //都在左边
            return lowestCommonAncestor(root.left, p, q);
        }else if(root.val < p.val && root.val < q.val){ //都在右边
            return lowestCommonAncestor(root.right, p, q);
        }else{

aquawj

//题意是找最小的，找完之后找next最小的
//要求：O(h) space， O(1) time
   10
 /    \
1      11
 \       \
  6       12
//BSTIterator iterator = new BSTIterator();
//int smallest = iterator.next();     smallest值为1
//int secondSmall = iterator.next();  secondsmall值为6

aquawj

//判断t是不是s的子树
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null) return false;
        if(t == null) return true; // null是其他的子集
        if(isSameTree(s, t)) return true; // 两棵树相等
        if(isSubtree(s.left, t) || isSubtree(s.right, t)) return true; //isLeft() or isRight()
        return false;
    }
    public boolean isSameTree(TreeNode root1, TreeNode root2){