写在前面

开个贴记录一下 刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

• 贪心算法：https://www.nowcoder.com/discuss/1051877
• 双指针：https://www.nowcoder.com/discuss/1057237
• 二分查找：https://www.nowcoder.com/discuss/1059986
• 排序：https://www.nowcoder.com/discuss/1063581
• 搜索：https://www.nowcoder.com/discuss/1069407
• 动态规划：https://www.nowcoder.com/discuss/1071676
• 分治法：https://www.nowcoder.com/discuss/1091335
• 链表：https://www.nowcoder.com/discuss/post/419235544456052736

树的结构

树的递归

No.1 Maximum Depth of Binary Tree

题目：https://leetcode.com/problems/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) {
        return root == null ? 0 : (1 + Math.max(maxDepth(root.left),maxDepth(root.right)));
    }
}

No.2 Balanced Binary Tree

题目：https://leetcode.com/problems/balanced-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 boolean isBalanced(TreeNode root) {
        return helper(root) != -1;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if (left == - 1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left,right) + 1;
    }
}

No.3 Diameter of Binary Tree

题目：https://leetcode.com/problems/diameter-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 {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return res;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        res = Math.max(res,left+right);
        return 1 + Math.max(left,right);
    }
}

No.4 Path Sum III

题目：https://leetcode.com/problems/path-sum-iii/

解题思路：

/**
 * 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 pathSum(TreeNode root, int targetSum) {
        return root == null ? 0 : (int)(pathSumWithRoot(root,targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum));
    }
    private long pathSumWithRoot(TreeNode root, long targetSum) {
        if (root == null) return 0;
        long count = 0;
        if (root.val == targetSum) {
            count = 1;
        }
        count += pathSumWithRoot(root.left,targetSum - root.val);
        count += pathSumWithRoot(root.right,targetSum - root.val);
        return count;
    }
}

No.5 Symmetric Tree

题目：https://leetcode.com/problems/symmetric-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 boolean isSymmetric(TreeNode root) {
        return root == null ? true : isSymmetric(root.left,root.right);
    }
    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
    }
}

No.6 Delete Nodes And Return Forest

题目：https://leetcode.com/problems/delete-nodes-and-return-forest/

解题思路：

递归先处理后续的子节点，拿到后续的节点的root时假定他们已经处理好了应该删除的元素，然后再去判断这个元素是否要被删除

/**
 * 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<TreeNode> tree = new ArrayList<TreeNode>();
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> to_delete_set = new HashSet<Integer>();
        for (int i : to_delete) {
            to_delete_set.add(i);
        }
        root = helper(root,to_delete_set);
        if (root != null) {
            tree.add(root);
        }
        return tree;
    }
    private TreeNode helper(TreeNode root, Set<Integer> dic) {
        if (root == null) {
            return null;
        }
        root.left = helper(root.left, dic);
        root.right = helper(root.right, dic);
        if (dic.contains(root.val)) {
            if (root.left != null) {
                tree.add(root.left);
            }
            if (root.right != null) {
                tree.add(root.right);
            }
            root = null;
        }
        return root;
    }
}

No.7 Invert Binary Tree

题目链接：https://leetcode.com/problems/invert-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 TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = invertTree(root.right);
        root.right = invertTree(root.left);
        root.left = temp;
        return root;
    }
}

No.8 Merge Two Binary Trees

题目链接：https://leetcode.com/problems/merge-two-binary-trees/submissions/

解题思路：

/**
 * 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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 == null || root2 == null) return root1 == null ? root2 : root1;
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

No.9 Subtree of Another Tree

题目：https://leetcode.com/problems/subtree-of-another-tree/submissions/

解题思路：

/**
 * 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 isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSub(root,subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    } 
    public boolean isSub(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (root.val == subRoot.val) {
            return isSub(root.left, subRoot.left) && isSub(root.right, subRoot.right);
        } else {
            return false;
        }
    }
}

No.10 Sum of Left Leaves

题目链接：https://leetcode.com/problems/sum-of-left-leaves/

解题思路：

/**
 * 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 sumOfLeftLeaves(TreeNode root) {
        if (root.left == null && root.right == null) return 0;
        return helper(root.left, true) + helper(root.right, false);
    }
    public int helper(TreeNode root, boolean isLeft) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return isLeft ? root.val : 0;
        return helper(root.left, true) + helper(root.right, false);
    }
}

树的层次遍历

No.1 Average of Levels in Binary Tree

题目链接：https://leetcode.com/problems/average-of-levels-in-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 List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        List<Double> res = new LinkedList<Double>();
        que.add(root);
        while(que.size() != 0) {
            int size = que.size();
            long sum = 0;
            for(int i = 0; i < size; i ++) {
                TreeNode cur = que.poll();
                sum += cur.val;
                if (cur.left != null) {
                    que.offer(cur.left);
                }
                if (cur.right != null) {
                    que.offer(cur.right);
                }
            }
            res.add((sum * 1.0) / (size * 1.0));
        }
        return res;
    }
}

No.2 Find Bottom Left Tree Value

题目链接：https://leetcode.com/problems/find-bottom-left-tree-value/submissions/

解题思路：

queque先入后出

/**
 * 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 findBottomLeftValue(TreeNode root) {
        if (root.left == null && root.right == null) return root.val;
        Queue<TreeNode> que = new LinkedList<TreeNode> ();
        que.offer(root);
        TreeNode temp = null;
        while(que.size() != 0) {
            int size = que.size();
            temp = que.peek();
            for (int i = 0; i < size; i++) {
                TreeNode cur = que.poll();
                if (cur.left != null) que.offer(cur.left);
                if (cur.right != null) que.offer(cur.right);
            }
        }
        return temp == null ? 0 : temp.val;
    }
}

树的前中后序遍历

前序遍历是父节点-》左子节点-〉右子节点

中序遍历是左子节点-》父节点-〉右子节点

后序遍历是左子节点-》右子节点-〉父节点

No. 1 Construct Binary Tree from Preorder and Inorder Traversal

题目：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-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 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        return helper(preorder,0,len - 1,inorder,0,len - 1,len);
    }
    private TreeNode helper(int[] preorder,int pl,int pr, int[] inorder, int il,int ir,int n) {
        if (pl >= n || il >= n || pl < 0 || il < 0 || pl > pr || il > ir) return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int len = pr - pl + 1;
        if (len == 1) return root;
        int i = 0;
        for (; i < len; i++) {
            if (inorder[i + il] == preorder[pl]) {
                break;
            }
        }
        root.left = helper(preorder,1+pl,i+pl,inorder,il,i - 1+il,n);
        root.right = helper(preorder,i+1+pl,len - 1+pl,inorder,i+1+il,len - 1+il,n);
        return root;
    }
}

No.2 Binary Tree Preorder Traversal

题目：https://leetcode.com/problems/binary-tree-preorder-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> res = new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return res;
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    }
}

非递归：

递归的本质是栈的调用，可以用栈来实现。注意栈是先入后出，要先把right塞入栈才是前序遍历

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) return res;
        Stack<TreeNode> sta = new Stack<TreeNode>();
        sta.push(root);
        while (!sta.empty()) {
            TreeNode cur = sta.pop();
            res.add(cur.val);
            if (cur.right != null) {
                sta.push(cur.right);
            }
            if (cur.left != null) {
                sta.push(cur.left);
            }
        }
        return res;
    }
}

No.3 Construct Binary Tree from Preorder and Postorder Traversal

题目：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-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 {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return helper(preorder,0,preorder.length - 1,postorder, 0, postorder.length - 1);
    }
    private TreeNode helper(int[] preorder,int preS, int preE,int[] postorder, int postS, int postE) {
        if (preE >= preorder.length || postE >= preorder.length || preS > preE || postS > postE) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preS]);
        if (preS == preE) {
            return root;
        }
        int leftPreRoot = preS + 1;
        int leftPostRoot = postS;
        for (; leftPostRoot <= postE; leftPostRoot++) {
            if (postorder[leftPostRoot] == preorder[leftPreRoot]) {
                break;
            }
        }
        int leftPreEnd = leftPostRoot - postS + leftPreRoot;
        root.left = helper(preorder,leftPreRoot, leftPreEnd,
                          postorder,postS,leftPostRoot);
        root.right = helper(preorder,leftPreEnd+1,preE,
                           postorder,leftPostRoot + 1,postE -1);
        return root;
    }
}

No.4 Construct Binary Tree from Inorder and Postorder Traversal

题目：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-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 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder,0,inorder.length - 1,postorder,0,postorder.length - 1);
    }
    private TreeNode helper(int[] inorder,int inS,int inE, int[] postorder, int postS,int postE) {
        if (inE > inorder.length - 1 || postE > postorder.length - 1 || inS > inE || postS > postE) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postE]);
        if (inS == inE) return root;
        int inRoot = inS;
        for (;inRoot <= inE; inRoot++) {
            if (inorder[inRoot] == postorder[postE]) {
                break;
            }
        }
        int postLeftE = postS + inRoot - 1 - inS;
        root.left = helper(inorder,inS,inRoot - 1,
                          postorder,postS,postLeftE);
        root.right = helper(inorder,inRoot+1,inE,
                           postorder,postLeftE+1,postE - 1);
        return root;
    }
}

No.5 Binary Tree Inorder Traversal

题目：https://leetcode.com/problems/binary-tree-inorder-traversal/

解题思路：

/**
 * Definition for a binary tree node.
 * public class reeNode {
 *     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> res = new LinkedList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        while(s.size() != 0) {
            TreeNode cur = s.peek();
            while(cur.left != null) {
                s.push(cur.left);
                cur = cur.left;
            }
            res.add(cur.val);
            s.pop();
            if (cur.right != null) s.push(cur.right);
        }
        return res;
    }
}

No. 6 Binary Tree Postorder Traversal

题目：https://leetcode.com/problems/binary-tree-postorder-traversal/

题目解析：

这里利用了 java 的 linkedlist 有 addFirst() 方法

/**
 * 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 {
    LinkedList<Integer> res = new LinkedList<Integer> ();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return res;
        Stack<TreeNode> sta = new Stack<TreeNode>();
        sta.push(root);
        while(!sta.isEmpty()) {
            TreeNode cur = sta.pop();
            res.addFirst(cur.val);
            if (cur.left != null) {
                sta.push(cur.left);
            }
            if (cur.right != null) {
                sta.push(cur.right);
            }
        }
        return res;
    }
}

二叉查找树

No.1 Recover Binary Search Tree

题目：https://leetcode.com/problems/recover-binary-search-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 {
    TreeNode pre, mis1, mis2;
    public void recoverTree(TreeNode root) {
        inorder(root);
        if (mis2 != null && mis1 != null) {
            int temp = mis2.val;
            mis2.val = mis1.val;
            mis1.val = temp;
        }
        return;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (pre != null && pre.val > root.val) {
            mis1 = mis2 == null ? pre : mis1;
            mis2 = root;
        }
        pre = root;
        inorder(root.right);
    }
}

No.2 Trim a Binary Search Tree

题目链接：https://leetcode.com/problems/trim-a-binary-search-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 TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            return trimBST(root.left, low, high);
        } else if (root.val == low) {
            root.right = trimBST(root.right,low, high);
            root.left = null;
        } else if (root.val == high) {
            root.left = trimBST(root.left,low, high);
            root.right = null;
        } else {
            root.left = trimBST(root.left,low,high);
            root.right = trimBST(root.right,low, high);
        }
        return root;
    }
}

No.3 Convert BST to Greater Tree

题目链接：https://leetcode.com/problems/convert-bst-to-greater-tree/

解题思路：

利用bst的中序遍历是递增数组的特性，逆者中序遍历遍历一遍即可

/**
 * 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 TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        if (root.left == null && root.right == null) return root;
        helper(root,0);
        return root;
    }
    public int helper(TreeNode root,int plus) {
        if (root == null) return 0;
        if (root.right != null) {
            root.val += helper(root.right,plus);
        } else {
            root.val += plus;
        }
        if (root.left != null) {
            return helper(root.left,root.val);
        } else {
            return root.val;
        }
    }
}

No.4 Lowest Common Ancestor of a Binary Search Tree

题目链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

解题思路：

利用bst的特性进行查找

/**
 * 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.val == p.val || root.val == q.val) return root.val == p.val ? p : q;
        if ((root.val > p.val && root.val < q.val) || (root.val < p.val && root.val > q.val)) {
            return root;
        } else 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);
        }
        return null;
    }
}

No.5 Minimum Absolute Difference in BST

题目：https://leetcode.com/problems/minimum-absolute-difference-in-bst/

解题思路：

/**
 * 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 {
    int min = Integer.MAX_VALUE;
    int pre = -1;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return Integer.MAX_VALUE;
        getMinimumDifference(root.left);
        if (pre != -1) {
            min = Math.min(min,root.val - pre);
        }
        pre = root.val;
        getMinimumDifference(root.right);
        return min;
    }
}

No.6 Lowest Common Ancestor of a Binary Tree

题目：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/

解题思路：

令左子树找到为left，右子树找到为right，中间符合为mid，mid+left+right >= 2 即可找到了lca

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        boolean flag = helper(root,p,q);
        return flag ? res : null;
    }
    private boolean helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        int mid = (root == p || root == q) ? 1 : 0;
        int left = helper(root.left,p,q) ? 1 : 0;
        int right = helper(root.right,p,q) ? 1 : 0;
        if (mid + left + right >= 2) {
            res = root;
        } 
        return (mid + left + right) > 0;
    }
}

No.7 Convert Sorted List to Binary Search Tree

题目链接：https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

题目解析：

为了让bst平衡，需要找到list的中点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * 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 TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = new ListNode(0);
        pre.next = slow;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        pre.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

No.8  Increasing Order Search Tree

题目链接：https://leetcode.com/problems/increasing-order-search-tree/

题目解析：

solution1:linkedlist 存储 再转为TreeNode，

/**
 * 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 {
    LinkedList<TreeNode> res = new LinkedList<TreeNode>();
    public TreeNode increasingBST(TreeNode root) {
        inorder(root);
        TreeNode head = new TreeNode(0);
        TreeNode cur = head;
        for (TreeNode node : res) {
            cur.right = new TreeNode(node.val);
            cur = cur.right;
        }
        return head.right;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        if (root.left != null) inorder(root.left);
        res.add(root);
        if (root.right != null) inorder(root.right);
    }
}

solution2:TreeNode inorder遍历的同时注意指针关系，将遍历的指针.left 赋值为null，不然会有环出现

/**
 * 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 {
    TreeNode res = new TreeNode(0);
    TreeNode head = res;
    public TreeNode increasingBST(TreeNode root) {
        inorder(root);
        return res.right;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        if (root.left != null) inorder(root.left);
        root.left = null;
        head.right = root;
        head = root;
        if (root.right != null) inorder(root.right);
    }
}

No.9 Two Sum IV - Input is a BST

题目：https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

解题思路：

Solution1: inorder取出list则是升序，前后两个指针ij去找sum = k

/**
 * 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<Integer>();
    public boolean findTarget(TreeNode root, int k) {
        inorder(root);
        for (int i = 0, j = list.size() - 1; i < j; ) {
            int res = list.get(i) + list.get(j);
            if (res == k) return true;
            if (res < k) i++;
            else j--;
        }
        return false;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}

Solution2: 利用hashset存储已经遍历过的值，每次用k-root.val的值去hashset里寻找值

/**
 * 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<Integer>();
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<Integer>();
        return dfs(root,k,set);
    }
    private boolean dfs(TreeNode root, int k, HashSet<Integer> set) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        return dfs(root.left,k,set) || dfs(root.right,k,set);
    }
}

No.10 Delete Node in a BST

题目链接：https://leetcode.com/problems/delete-node-in-a-bst/

解题思路：

先找到key，然后在删除时有以下几种情况

• left right 为空，return null
• left 为空 right 不为空，return right
• left 不为空 right 为空，return left
• left 不为空 right 不为空，找到 right 的最小值，将right的最小值赋值给root。val进行替换，随后删除right中的最小值

/**
 * 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 TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) { 
            if (root.left == null && root.right == null) return null;
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right,minNode.val);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            root.left = deleteNode(root.left, key);
        }
        return root;
    }
    private TreeNode findMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

}

字典树Trie

字典树用来判断字符串是否存在或者是否具有某种字符串前缀的问题

No.1 Implement Trie (Prefix Tree)

题目链接：https://leetcode.com/problems/implement-trie-prefix-tree/

解题思路：

class TrieNode {
    TrieNode[] list;
    boolean is_val;
    public TrieNode() {
        list = new TrieNode[26];
    }
}

class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.list[c - 'a'] == null) {
                cur.list[c - 'a'] = new TrieNode();
            } 
            cur = cur.list[c - 'a'];
        }
        cur.is_val = true;
    }
    
    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.list[c - 'a'] == null) {
                return false;
            }
            cur = cur.list[c - 'a'];
        }
        return cur.is_val;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (int i = 0;i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.list[c - 'a'] == null) {
                return false;
            }
            cur = cur.list[c - 'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */