这题让判断二叉树是否对称，如果只有一个节点是没法判断的，所以根节点不需要判断，只需要判断两个子节点的值是否相等，但子节点的子节点也需要判断，我们可以使用递归的方式，判断的原则是：  左子节点的左子节点和右子节点的右子节点比较。 左子节点的右子节点和右子节点的左子节点比较。  如下图所示：   public boolean isSymmetrical(TreeNode pRoot) { if (pRoot == null) return true; // 从两个子节点开始判断 return dfs(pRoot.left, pRoot.right); } private boolean dfs(T...

这题让对二叉树进行层序遍历，实际上就是二叉树的 BFS （宽度优先搜索，也叫广度优先搜索）遍历，需要使用一个队列，来记录每层的节点，遍历当前节点之后，需要把它的两个子节点（如果不为空）添加到队列中，每层都需要创建一个集合，每层的节点需要放到对应的集合中。 怎么确定每层有多少节点呢？实际上在每层遍历开始之前就要先记录下该层的节点个数，步骤如下图所示：    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> an...

这题让按照之字形顺序打印二叉树，也就是先从左往右打印，接着下一层在从右往左打印，在下一层又从左往右打印……，就这样左右来回交替的方式。 这里我们可以使用双端队列：  如果当前层是从左往右打印，那么它的子节点要从左往右添加到队列的尾部。 如果当前层是从右往左打印，那么它的子节点要从右往左添加到队列的头部。  如下图所示：   public ArrayList<ArrayList<Integer>> Print(TreeNode root) { ArrayList<ArrayList<Integer>> ans = new ArrayList<...

这题让计算二叉树的深度，如果节点为空，则深度为 0 ，否则我们通过递归的方式分别计算左子树和右子树的深度，那么二叉树的最大深度就是取两个子树的最大深度加 1 ，这个 1 就是当前节点贡献的深度，如下图所示：   public int maxDepth(TreeNode root) { if (root == null) return 0; // 递归，取左右子树的最大深度加 1 。 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }   public: int maxDepth(TreeNode *root) { ...

这题说的是根据前序遍历数组和中序遍历数组来重建二叉树。我们知道前序遍历数组的第一个元素一定是根节点，在中序遍历数组中，根节点前面的都是根节点左子树上的节点，根节点后面的都是根节点右子树上的节点。左右两棵子树我们可以使用递归的方式继续创建。 我们首先使用前序数组的第一个元素创建根节点，然后查询该节点在中序遍历数组中的位置，把中序数组分成两部分，一部分是根节点左子树的节点，一部分是根节点右子树的节点。为了方便查询，我们可以提前把中序数组存储到 map 中。  比如前序数组是：{1,2,4,7,3,5,6,8}，中序数组是：{4,7,2,1,5,3,8,6} 那么 1 就是根节点，中序数组中 1 左...

这题说的是把升序数组转化为二叉搜索树，所谓的二叉搜索树就是左子节点都比根节点值小，右子节点都比根节点值大，并且每一颗子树也都满足这个条件。 因为题中已经说了是有序数组，我们每次只需要取数组中间的值创建一个节点 node ，中间值左边的是 node 的左子节点，右边的是 node 的右子节点，node 的左右子树可以使用递归的方式继续创建，步骤如下图所示：   public TreeNode sortedArrayToBST(int[] nums) { if (nums.length == 0) return null; return sortedArrayToBST(nums, 0, nums...

这题让计算两个字符串相乘并且不能使用内置的库函数。如果是单个数字乘以一个字符串，可以使用两个指针一个记录相乘的结果，一个记录进位的值，然后不停的把结果保存下来即可，如下图所示：  如果是多位数字相乘也可以参照单个数字相乘的步骤，每次使用乘数中的其中一位和被乘数相乘。这里的关键点是找出相乘之后应该存放的位置，我们使用一个一维数组来记录。 如下图所示，如果被乘数的第 i 位（从右边数）和乘数的第 j 位（从右边数）相乘，相乘的结果应该放到数组的第 i+j 位（从右边数），注意存放的时候还要加上数组中原来的值，如果结果大于等于 10 ，要取个位数字，然后往前进位。  因为字符串的读取都是从左边开始读...

这题说的是找出所有路径和为 target 的路径，这里的路径只能从根节点到叶子节点，这题和上一题类似：《二叉树中和为某一值的路径》。 我们从根节点开始往下累加路径上的节点值，并且还要记录这条路径上的节点，到叶子节点的时候如果累加的值等于 target ，说明这条路径就是我们找的，保存这条路径。 我们使用的是 List （Java语言使用的是List，C++使用的是Vector）来存储路径上的节点，因为它是引用传递，所以递归往下走的时候我们选择节点，递归往回走的时候要撤销选择。   public ArrayList<ArrayList<Integer>> FindPath...

这题让判断的是从根节点到叶子节点的所有路径中，有没有和等于 sum 的路径，我们使用 DFS 从根节点开始遍历，每到一个节点就用 sum 减去该节点的值，如果到叶子节点， sum 正好等于叶子节点的值，则存在这样的路径。 如下图所示，有两个叶子节点的值等于 sum ，说明有两条这样的路径，实际上只要存在一条即可返回 true 。   public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; // 如果到叶子节点了，并且剩余值等于叶子节点的值，返回true。 if (root.left ...

买卖股票的题大概有 6 道，可以使用动态规划全部解决，但这题是最简单的一道，如果使用动态规划，有点杀鸡用牛刀了，没必要。 这题说的是只能交易一次，求所获得的最大利润，也就是在最低价的时候买入，在后面最高价的时候卖出，我们可以使用一个变量 minV 来记录前面遍历过的最小值，这个最小值不是固定的，也是会跟着变动的，然后用数组后面的值减去这个最小值差，这个差就是利润，我们只需要保存最大利润即可。  public int maxProfit(int[] prices) { int minV = prices[0];// 遍历过的最小值 int ans = 0; for (int price : pr...

这题说的是找出二叉树的最大路径和，这里的最大路径不一定经过根节点，所以我们可以采用自下往上的遍历方式来计算， 对于当前节点：  如果它的两个子节点路径都是负的，就没必要选择了，因为如果是负数，越选择和就会越小，如下图中的第 1 种情况。 如果它的两个子节点路径一个是正的，一个是负的，我们只需要选择正的即可，如下图中的第 2 种情况。 如果它的两个子节点都是正的，我们可以都选择，也可以选择其中的一个子节点，如下图中的第 3 种情况。  最后我们只需要保存选择的最大值即可，对于第 1 ，2 两种情况，我们还可以接着往上继续选择，但对于第 3 种情况，如果两个子节点都选择了，就不能再往上选了，分支会...

这题说的是计算从根节点到叶子节点的所有路径和，实际上每一条从根节点到叶子节点都构成了一个数字，累加这些数字即可，这些数字只有在叶子节点才能累加，如下图所示。    public int sumNumbers(TreeNode root) { return dfs(root, 0); } private int dfs(TreeNode root, int sum) { if (root == null) // 终止条件 return 0; // 计算当前节点的值 sum = sum * 10 + root.val; // 如果当前节点是叶子节点，说明找到了一条完整路径， // 直接返回这条路径...

这题要找出链表中环的入口，如果链表中没有环，则返回空。前面我们讲过《判断链表是否有环》，所以我们可以根据前面的解来判断链表是否有环，如果没环，自然就不可能有环的入口。如果有环我们再来找出环的入口，怎么找呢？如下图所示。  在相遇点快指针走过的距离是： a+c+(b+c)*m，其中 b+c 是环的周长， m 是快指针在环上转了 m 圈之后和慢指针相遇。慢指针走过的距离是： a+c+(b+c)*n，其中 n 是慢指针在环上转了 n 圈之后和快指针相遇，很明显 n < m 。 由于快指针每次走两步，慢指针每次走一步，所以快指针走的距离是慢指针的 2 倍，也就是： a+c+(b+c)*m = 2...

这题让判断链表是否有环，我们可以使用两个指针从链表的头节点开始往后走，一个是慢指针每次只能走一步，一个是快指针，每次只能走两步。 如果链表没有环，如下图所示，最终快指针有可能会指向空，也有可能当快指针指向最后一个节点的话，就没法往后走了。   如果链表有环，无论是快指针还是慢指针都永远不可能指向空，最终它们都会走到环上，因为慢指针每次走 1 步，快指针每次走 2 步，所以在环上的时候每走 1 次，它俩之间的距离就会缩小 1 ，无论它俩相差多远，最终一定会在环上相遇。  所以如果快慢指针相遇了，肯定是有环的，如果快指针指向空了，或者不能再往下走了，说明没有环。  public boolean h...