考察知识点： 递归、深度优先搜索 题目分析：  可以从root节点开始，若存在以该节点为根节点的树到其某个子节点有满足条件的路径，则返回true；否则分别以该节点的左右子树为根节点重新计算。  那么怎样判断是否存在一个以root为根节点的树到其某个子节点的路径满足条件呢？实际上和题目牛的奶量统计类似，但是本题是从一个节点到其任意子节点，而“牛的奶量统计”则是从根节点到叶子节点。  对每一个以root为根节点的树，设其值为root->val，那么只要左子树或者右子树中能有一条从根节点到其任意子节点的路径和为target - root->val，原树也就能够满足条件。  所用编程语言：...

考察知识点： 递归、深度优先搜索 题目分析：  对每一个以root为根节点的树，设其值为root->val，那么只要左子树或者右子树中能有一条从根节点到叶子节点的路径和为target - root->val，原树也就能够满足条件。   注意条件：叶子节点（左右子树均为空），目标和为0 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(null...

考察知识点： 递归、深度优先搜索、二叉树 题目分析：  原树的中的最短路径可以由子树中的最短路径得到。   需要考虑的是，递归的基准条件是怎样的？  如果给定的是一棵空树，那么它的最短路径就是0； 如果一棵子树，它没有左孩子，但是有右孩子。我们在取左右子树的最短路径时，发现会取到左子树，因为该子树的最短路径为0，这是不对的。取左子树没有满足题目中要求的“从根节点到叶子节点的最短路径”，而是中途停下来了。下图中标绿色的是叶子节点，可以看到不能取左子树，而应该取右子树的最短路径。    同理，当一棵子树只有左孩子，没有右孩子时，应该取左孩子的最短路径。  所用编程语言： C++ /** * str...

考察知识点： 二叉树、队列、广度优先搜索 题目分析：  题目的要求是将一段数组中的值按0和1分到二叉树上，例如：   还要求是完全二叉树，可以根据层序遍历的思想，利用两个队列分别建立左右子树，左子树保存0，右子树保存1。队列中存储非空指针，对每一个新的数，尝试将其放入队列中首个结点的左孩子和右孩子，如果右孩子已经有值，将队列pop并获得队列中下一个结点重新操作即可。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x)...

考察知识点： 深度优先搜索、递归 题目分析：  函数maxDepth返回的是一棵树的最大深度。所以，如果我们现在已经知道某棵树的左子树和右子树的最大深度，那么这棵树的最大深度就是： maxDepth = 1 + max(maxDepth(root->left), maxDepth(root->right)); 即看左子树和右子树哪一个深，然后再加上root所占的一层深度即是以root为根节点的树的最大深度。  该递归的基准情况即root为空树，那么它的深度为0。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct Tree...

考察知识点： 中序遍历、二叉搜索树 题目分析： 方法1  题目中要求出第k重的牛牛。实际上，对于一棵二叉搜索树，它的中序遍历是递增的。例如 1,2,3,4,5,6   因此，可以通过中序遍历得到二叉搜索树中的第k大的数。为了找到第k大的数，需要遍历所有结点，放到vector中进行下一步处理。 方法2  可以发现，如果反过来遍历啊，那么就能得到递减的序列：  这种遍历方法就是：先遍历右子树，然后遍历根节点，之后遍历左子树。 所用编程语言： C++ 方法1代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct ...

考察知识点： 中序遍历、递归、二叉搜索树 题目分析：  题目中要求出第k轻的牛牛。实际上，对于一棵二叉搜索树，它的中序遍历是递增的。例如 1,2,3,4,5,6   因此，可以通过中序遍历得到二叉搜索树中的第k小的数。  中序遍历即先访问左子树，然后访问根节点，之后访问右子树。在代码中按照这个顺序进行递归即可。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), ri...

考察知识点： 深度优先搜索、递归 题目分析：  只要该树中的每一个子树（包含本身）都是二叉搜索树，那么原来的树就是一棵二叉搜索树。该题可以使用递归来解。  使用递归解题时，可以先考虑特殊情况。当root是空树时，满足二叉搜索树的条件。当root有左孩子并且左孩子的值不小于root的值，那么就不满足二叉搜索树的条件。同理，若root有右孩子并且右孩子的值不大于root的值，那么也不满足二叉搜索树的条件。  而在一般情况下，root的左右孩子结点满足二叉搜索树的情况，下一步就是要确定左右子树是否是二叉搜索树。由于函数isValidBST返回的是一棵树是否是二叉搜索树，可以将左右子树作为根节点进行递...

考察知识点： 广度优先搜索、树的层序遍历、STL 题目分析：  本题要求求出二叉树中和最大的那一层。可以层序遍历这个二叉树，遍历过程中维护重量级的那一层的数值和索引。  树的层序遍历一般使用一个队列，先将头节点放入队列中，然后对队列中的每个元素，首先访问这个元素，然后将该元素的左右孩子结点放入队列中，直至队列中为空。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr),...

考察知识点： 广度优先搜索、树的层序遍历、STL 题目分析：  树的层序遍历一般使用一个队列，先将头节点放入队列中，然后对队列中的每个元素，首先访问这个元素，然后将该元素的左右孩子结点放入队列中，直至队列中为空。  这道题在树的层序遍历的基础之上提出进行Z字形遍历的要求。我们使用一个bool控制加入到vector中的顺序。由于层序遍历的顺序本身是确定的，但是由于该层中的元素数量是已知的，我们可以提前确定vector的大小，在需要时将结点值从尾向前加入到vector中。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNod...

考察知识点： 树的层序遍历、广度优先搜索、STL 题目分析：  该题目就是层序遍历一下树，将树的每一层输出。  层序遍历一般使用一个队列，首先将头节点放入队列中，然后对于队列中的节点，先访问这个节点，然后将其从队列中删去并将其左右节点放入队列中。  为了确定在队列中的节点所处的层，使用size记录该层的大小，每遍历完一次size就开始遍历下一层，直至某一层中全部为空节点。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int...

考察知识点： 树的遍历、深度优先搜索、递归 题目分析：  可以自己先画一画图，例如下图：   容易发现，每一棵子树中的左右子节点都只是调换了左右位置。所以我们可以通过递归的方式，从下往上依次交换左右节点的相对位置。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: ...

考察知识点： 树的层序遍历、STL、宽度优先搜索 题目分析：  判断树是否是对称结构，可以通过遍历每一层，判断每一层中的结点是否是回文串来解决。  层序遍历时，一般需要使用队列，从头节点考试，将一层中节点的下一层节点放入队列中，直到队列为空时停止。  为了判断树的结构是否是对称的，我们需要记录某个节点的位置（是左子树的根节点还是右子树的根节点），可以通过将nullptr记录成#，这样就保留了树中节点的结构。  每次层序遍历时，首先获记录该层的节点数。因为每遍历到一个值，就需要将他的子树都加进来，这些节点都保存到队列中，通过记录的节点数可以明确哪些节点是属于某一层的。遍历完这一层后判断使用这一层...

考察知识点： 树的遍历、递归、深度优先搜索 题目分析：  注意题目中牛只在叶子上，所以只有叶子上的编号有效。  可以通过递归的方式，找到树1从左向右深度优先搜索找到的叶子，找到树2从右向左深度优先搜索找到的叶子，将这些叶子放到数组中，然后再比较叶子是否相同。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ cla...