目录
- 杨辉三角
- 题目描述
- 解题思路
- 解题代码
- 相同的树
- 题目描述
- 解题思路
- 二叉树的层序遍历
- 题目描述
- 解题思路
- 解题代码
- 从底层层序遍历
- 二叉树的最近公共祖先
- 题目描述
- 解题思路
- 从前序与中序遍历序列构建二叉树
- 题目描述
- 解题思路
- 从后序与中序遍历序列构建二叉树
- 题目描述
- 解题思路
- 根据二叉树创建字符串
- 题目描述
- 解题思路
杨辉三角
链接：杨辉三角
题目描述
题目描述如下：
在杨辉三角中当前数等于上一行的同一个列数和其前面一个数的和。
左右边界为1。
解题思路
解题思路如下：
我们使用顺序表
- 先把
解题代码
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> list = new ArrayList<>();
//先把第一行安排
list.add(1);
ret.add(list);
//处理后面除最后一个
for(int i = 1; i < numRows; i++) {
//记录当前行，并将第一个给1
List<Integer> nowRow = new ArrayList<>();
nowRow.add(1);
//记录上一行
List<Integer> perRow = new ArrayList<>();
perRow = ret.get(i-1);
//重第二个元素录入
for(int j = 1; j < i; j++) {
Integer a = perRow.get(j) + perRow.get(j-1);
nowRow.add(a);
}
//最后一个给1
nowRow.add(1);
ret.add(nowRow);
}
return ret;
}
}
相同的树
链接：相同的树
题目描述
解题思路
判断只有以下四种情况：
- 两个树都为空。
- 其中一棵树为空。
- 当前节点值相同，递归调用判断左子树和右子树。
- 当前节点值不同，返回false。
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
//两个树都为空
if(p == null && q == null) return true;
//其中一棵树为空
if((p == null && q != null) || (p != null && q == null)) return false;
//值相同
if(p.val == q.val) {
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
//值不同
return false;
}
}
二叉树的层序遍历
链接：二叉树的层序遍历
题目描述
解题思路
解题思路如下：
- 先创建一个二维数组，如果树为空，就返回空的二维数组，不要返回null。
- 再根据层序遍历思路，将根结点入队，循环遍历直到队列为空。
- 求当前队列的长度，以长度为循环条件（因为如此每次循环都将只保留本次循环入队的元素）取出队列的元素，放入一维数组，并将该元素不为空的左右孩子入队。
- 每出一次循环就将一维数组存入二维数组。
解题代码
代码如下：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//结果数组
List<List<Integer>> ret = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return ret;//必须返回空的二维数组
}
queue.offer(root);
while(!queue.isEmpty()){
//每层数据
List<Integer> level = new ArrayList<Integer>();
int size = queue.size();
//根据每层元素数循环
while(size > 0){
TreeNode cur = queue.poll();
level.add(cur.val);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
ret.add(level);
}
return ret;
}
}
从底层层序遍历
链接：二叉树的层序遍历II
跟头层序遍历一样，只需要将插入ret结果时变为头插即可。
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return ret;//必须返回空的二维数组
}
queue.offer(root);
while(!queue.isEmpty()){
//每层数据
List<Integer> level = new ArrayList<Integer>();
int size = queue.size();
//根据每层元素数循环
while(size > 0){
TreeNode cur = queue.poll();
level.add(cur.val);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
ret.addFirst(level);
}
return ret;
}
}
二叉树的最近公共祖先
链接：二叉树的最近公共祖先
题目描述
描述如下图：
解题思路
我们先思考有哪些情况：
- 两个节点在其中一棵树的左右。
- 两个节点有一个节点是祖先。
思路：
- 先看树是否为空，为空返回null。
- 判断当前根节点是不是所求节点。
- 左子树右子树找祖先。
- 根据得到情况判断：
- 如果当前根节点左右都得到值，那根节点就是共同祖先，对应情况一。
- 如果只有一方有值，那该值就是共同祖先，对应情况二。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//树是否为空
if(root == null){
return null;
}
//根节点判断
if(root == p || root == q){
return root;
}
TreeNode retLeft = lowestCommonAncestor(root.left,p,q);
TreeNode retRight = lowestCommonAncestor(root.right,p,q);
if(retLeft != null && retRight != null){//根两边
return root;
//一个节点为祖先
}else if(retRight == null){
return retLeft;
}else{
return retRight;
}
}
}
从前序与中序遍历序列构建二叉树
题目描述
解题思路
前序遍历得到的节点顺序是 根节点，左子树，右子树。
中序遍历得到的节点顺序是 左子树，根节点，右子树。
- 先从前序遍历结果从前往后依次拿到节点。
- 将该节点作为根节点然后依次创建左子树右子树（因为前序遍历是根左右）。
- 我们在中序遍历结果中根节点左边就是左子树包含节点，根节点右边就是右子树包含节点，所以创建子树时将范围给进去。
易错点：如果前序遍历的下标不是成员变量而是局部变量，那么每次递归拿到的都是0。
class Solution {
private int preorderIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,inorder,0,inorder.length-1);
}
public TreeNode build(int[] preorder, int[] inorder, int begin, int end) {
//没有子树
if(begin > end) {
return null;
}
TreeNode root = new TreeNode(preorder[preorderIndex]);
preorderIndex++;
int rootIndex = findRootIndex(inorder,root.val,begin,end);
root.left = build(preorder,inorder,begin,rootIndex - 1);
root.right = build(preorder,inorder,rootIndex+1,end);
return root;
}
private int findRootIndex(int[] inorder, int val,int begin, int end) {
for(int i = begin; i <= end; i++){
if(inorder[i] == val) return i;
}
return -1;
}
}
从后序与中序遍历序列构建二叉树
题目描述
解题思路
中序遍历得到的节点顺序是 左子树，根节点，右子树。
后序遍历得到的节点顺序是 左子树，右子树，根节点。
依据前面的前序中序构建，我们只需要修改从后面开始遍历拿到后序遍历的结果在依次创建右子树，左子树即可。
class Solution {
public int postorderIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postorderIndex = postorder.length - 1;
return build(inorder,postorder,0,inorder.length-1);
}
private TreeNode build(int[] inorder, int[] postorder, int begin, int end) {
if(begin > end) return null;
TreeNode root = new TreeNode(postorder[postorderIndex]);
postorderIndex--;
int rootIndex = findRootIndex(inorder,root.val,begin,end);
root.right = build(inorder,postorder,rootIndex+1,end);
root.left = build(inorder,postorder,begin,rootIndex-1);
return root;
}
private int findRootIndex(int[] inorder, int val,int begin, int end) {
for(int i = begin; i <= end; i++){
if(inorder[i] == val) return i;
}
return -1;
}
}
根据二叉树创建字符串
题目描述
j
解题思路
节点有以下四种情况
- 如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号。
- 如果当前节点没有孩子，那我们不需要在节点后面加上任何括号。
- 如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号。
- 如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 ‘()’ 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。
class Solution {
public String tree2str(TreeNode root) {
StringBuilder str = new StringBuilder();
//没节点
if(root == null) {
return "";
}
str.append(root.val);
//没孩子
if(root.left == null && root.right == null) {
return str.toString();
}
//左孩子为空
if(root.left == null) {
str.append("()");
str.append("(");
str.append(tree2str(root.right));
str.append(")");
return str.toString();
}
//右孩子为空
if(root.right == null) {
str.append("(");
str.append(tree2str(root.left));
str.append(")");
return str.toString();
}
str.append("(");
str.append(tree2str(root.left));
str.append(")");
str.append("(");
str.append(tree2str(root.right));
str.append(")");
return str.toString();
}
}