import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param proot TreeNode类 * @param k int整型 * @return int整型 ...

import java.util.ArrayList; import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ // 层次遍历使用队列 // 难点在于如何划分层次：进入每一个层次之前，先统计一下队列长度 // 每层顺序不同：反转数组 // 时空复杂度：O（n） public class Solution { public ArrayList&l...

import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ // 难点在于要维护一个全局数组，不好递归 // 且在单条路径递归的时候，要维护一组局部的历史节点 // 时间复杂度O（n^2）,空间复杂度O（n） public class Solution { public ArrayList<ArrayList<Inte...

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ // 递归，把sum根据本级节点的值调整后向下传，把是否有符合题意的路径布尔值向上抛，终止条件：空节点或找到路径 // 时空复杂度：O（n） public class Solution { public boolean hasPathSum (TreeNode root, int sum) { // write code here if (root == n...

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ // 懒人编程法：自顶向下，把问题抛给子树 // 二叉搜索树的特性：按照前序遍历从小到大放置元素值，一个节点的左子树所有节点值都小于此节点值，小于右子树所有节点值。 // 比较p，q，根节点的值，如果p、q在根节点的两端，则根节点就是其第一个公共结点，如果在...

import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ // 队列层次遍历，双队列判断回文 // java中队列的两种实现：LinkedList可以有null元素，ArrayDeque不可以 // 时空复杂度：O（n） public class Solution { boolean isSymmetrical(TreeNode pRoot) {...

// 自顶向下，两个递归，第一个遍历所有节点，第二个获取子树的高度 // 时间复杂度O（n^2）,空间复杂度O（n） public class Solution { public Integer height(TreeNode root){ if (root == null){ return 0; } if (height(root.right) < height(root.left)) return height(root.left)+1; else return height(root.right)+1; } public boolean IsBalanced_Solution(Tr...

import java.util.ArrayList; import java.util.*; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ // 注意：队列适用于广度优先遍历 // 注意：不必出一进一，此例中就存在出一进二、出一进一、出一进零 // 时空复杂度O（n） public class Solution { public ArrayList<Integer...

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ // 递归心得：把本身的函数看作已经写好的来使用 // 递归操作：左右节点分别使用本函数之后，交换 终止条件：节点为空 // 时间和空间复杂度：O（n） public class Solution { public TreeNode Mirror (Tree...

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ // 使用递归的方法，迭代操作：比较和加一，终止条件：节点为空 // 在每个节点处比较一次并加一，因此时间复杂度为O（n），递归是一个栈，因此最坏情况的空间复杂度是O（n） public class Solution { public int TreeDepth(TreeNode root) { // 注意：此处判断节点是否为...

/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */ // 不难，遍历即可，注意判断先锋节点是否为空，时空复杂度均为O（n） public class Solution { public RandomListNode Clone(RandomListNode pHead) { // 先判断头结点 if(pHead == null) ret...

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ // 由于链表已经排序，重复值是连在一起的，所以遍历一遍，直接比较即可 // 虽然存在内循环，但是跳跃式的，可以替代原本的外循环，因此时间复杂度为O（n），空间复杂度为O（1） public class Solution { public ListNode deleteDuplication(ListNode pHead) { // 设置两个虚头结点 ListNode node_1 = new ...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param val int整型 * @return ListNode类 */ // 此题很简单，遍历链表，如果命中，no...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ // 此题的进阶版：使用快慢指针，快指针领先k-1步，当快指针到达链表最后一个非null节点的时候，慢指针也就到达倒数第k个了。时间复杂度仍然是O（n），但空间复杂度变为了O（1），比用栈要好。 // 快慢指针分两种，一种是快指针领先固定步数，一种是快指针前进速度快，可以一下前进2步 public class So...