目录
1. 相同的树
题目要求
?分析一下
?上代码
时间复杂度O（min（m，n））
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
// p!=null && q!=null 并且 p.val == q.val
return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
}
}?2. 另一颗树的子树
链接? ?572. 另一棵树的子树 - 力扣（LeetCode）
题目要求
?分析一下
时间复杂度O（m*n）
?上代码
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
// p!=null && q!=null 并且 p.val == q.val
return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null ) return false;
if(isSameTree(root,subRoot)) {return true;}
if(isSubtree(root.left,subRoot)) {return true;}
if(isSubtree(root.right,subRoot)) {return true;}
return false;
}
}3. 二叉树的最大深度?
链接? ?104. 二叉树的最大深度 - 力扣（LeetCode）
题目要求
上代码
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int leftTree = maxDepth(root.left);
int rightTree = maxDepth(root.right);
return (leftTree > rightTree ? leftTree+1 : rightTree+1 );
}
}?4. 平衡二叉树
链接? ?110. 平衡二叉树 - 力扣（LeetCode）
题目要求
? ?
?分析一下
?上代码
（1）时间复杂度O（n^2）
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int leftTree = maxDepth(root.left);
int rightTree = maxDepth(root.right);
return (leftTree > rightTree ? leftTree+1 : rightTree+1 );
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}(2)前面一种方法，每次每个结点都要算一次高度，比如刚开始算根节点时，已经把根节点的左子树结点算过了，而且如果前面左子树的子树不平衡，后面还要继续判断，每次这样做，就造成了空间上的浪费
那么我们可以在求高度时，顺序就可以判断是否平衡
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int leftTree = maxDepth(root.left);
int rightTree = maxDepth(root.right);
if (leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree - rightTree) <= 1) {
return Math.max(leftTree,rightTree) + 1;
}else {
return -1;
}
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return maxDepth(root) >= 0;
}
}5. 对称二叉树
链接? ?101. 对称二叉树 - 力扣（LeetCode）
题目要求
?分析一下
?上代码
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetricChild(root.left,root.right);
}
private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
if(leftTree == null && rightTree != null || rightTree == null && leftTree != null) {return false;}
if(leftTree == null && rightTree == null) {
return true;
}
if(leftTree.val != rightTree.val) {
return false;
}
return isSymmetricChild(leftTree.left,rightTree.right) &&
isSymmetricChild(leftTree.right,rightTree.left);
}
}6. 二叉树的构建及遍历
链接? ?二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
题目要求
?分析一下
?上代码
import java.util.*;
public class Main {
class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public int i = 0;
public TreeNode createTree(String s) {
TreeNode root = null;
if(s.charAt(i) != '#') {
root = new TreeNode(s.charAt(i));
i++;
root.left = createTree(s);
root.right = createTree(s);
}else{
i++;
}
return root;
}
public void inorder(TreeNode root) {
if(root == null) return;
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNextLine()) {
String s = scan.nextLine();
Main m = new Main();
TreeNode root = m.createTree(s);
m.inorder(root);
}
}
}7. 二叉树的层序遍历?
链接? ?102. 二叉树的层序遍历 - 力扣（LeetCode）
题目要求
?分析一下
这道题和前一篇写过的层序遍历唯一不同的地方就是
?上代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> row = new ArrayList<>();
while(size > 0) {
TreeNode cur = queue.poll();
size--;
row.add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
ret.add(row);
}
return ret;
}
}?
8. 二叉树的最近公共祖先
?链接??236. 二叉树的最近公共祖先 - 力扣（LeetCode）
题目要求
?分析一下
(1)方法一，看根结点是不是，递归左右子树
?（2）方法二，使用两个栈来找公共祖先
?上代码
?（1）方法一的代码
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 (retLeft != null) {
return retLeft;
}else {
return retRight;
}
}
}（2）方法二的代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null) {
return null;
}
Stack<TreeNode> stack1 = new Stack<>();
getPath(root,p,stack1);
Stack<TreeNode> stack2 = new Stack<>();
getPath(root,q,stack2);
int size1 = stack1.size();
int size2 = stack2.size();
//两个栈个数不一样
if(size1 > size2) {
int tmp = size1 - size2;
while(tmp != 0) {
stack1.pop();
tmp--;
}
}else {
int tmp = size2 - size1;
while(tmp != 0) {
stack2.pop();
tmp--;
}
}
//两个栈个数一样
while(!stack1.empty() && !stack2.empty()) {
if(stack1.peek() == stack2.peek()) {
return stack1.peek();
}else {
stack1.pop();
stack2.pop();
}
}
return null;//没有公共祖先
}
//找到根节点到指定节点路径上所有结点，放在栈中
private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if(root == null || node == null) {
return false;
}
stack.push(root);
if(root == node) {
return true;
}
boolean ret1 = getPath(root.left,node,stack);
//只能说明左边没有node
if(ret1) {
return true;
}
boolean ret2 = getPath(root.right,node,stack);
if(ret2) {
return true;
}
//根节点不是 根左不是 根右也不是
stack.pop();
return false;
}
}9. 二叉搜索树与双向链表
?链接? ?二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
题目要求
?分析一下
?上代码
public class Solution {
TreeNode prev = null;
public void ConvertChild(TreeNode root) {
if(root == null) return;
ConvertChild(root.left);
root.left = prev;
if(prev != null) {
prev.right = root;
}
prev = root;
ConvertChild(root.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
ConvertChild(pRootOfTree);
TreeNode head = pRootOfTree;
while(head.left != null) {
head = head.left;
}
return head;
}
}10. 从前序遍历与中序遍历序列构造二叉树
?链接? ?105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
题目要求
?分析一下
?上代码
class Solution {
public int preIndex = 0;
private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend){
//没有了左树或者没有了右树
if(inbegin > inend) {
return null;
}
TreeNode root = new TreeNode(preorder[preIndex]);
//找到当前根节点 在中序遍历中的位置
int rootIndex = findInorder(inorder,preorder[preIndex],inbegin,inend);
preIndex++;
root.left = buildTreeChild(preorder, inorder,inbegin,rootIndex-1);
root.right = buildTreeChild(preorder, inorder,rootIndex+1,inend);
return root;
}
private int findInorder(int[] inorder,int val,int inbegin,int inend){
for(int i = inbegin; i <= inend; i++) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
}11. 从中序遍历与后序遍历序列构造二叉树
?链接??106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
题目要求
?分析一下
?上代码
class Solution {
public int postIndex = 0;
private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
//没有了左树或者没有了右树
if(inbegin > inend) {
return null;
}
TreeNode root = new TreeNode(postorder[postIndex]);
//找到当前根节点 在中序遍历中的位置
int rootIndex = findInorder(inorder,postorder[postIndex],inbegin,inend);
postIndex--;
root.right = buildTreeChild(postorder, inorder,rootIndex+1,inend);
root.left = buildTreeChild(postorder, inorder,inbegin,rootIndex-1);
return root;
}
private int findInorder(int[] inorder,int val,int inbegin,int inend){
for(int i = inbegin; i <= inend; i++) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length-1;
return buildTreeChild(postorder,inorder,0,inorder.length-1);
}
}12. 根据二叉树创建字符串
?链接? ? ?606. 根据二叉树创建字符串 - 力扣（LeetCode）
?题目要求
分析一下
?上代码
class Solution {
public String tree2str(TreeNode root) {
StringBuilder sb = new StringBuilder();
tree2strChild(root,sb);
return sb.toString();
}
private void tree2strChild(TreeNode t, StringBuilder sb) {
if(t == null) return ;
sb.append(t.val);
if(t.left != null) {
sb.append("(");
tree2strChild(t.left,sb);
sb.append(")");
}else {
if(t.right == null) {
return;
}else {
sb.append("()");
}
}
if(t.right == null) {
return;
}else {
sb.append("(");
tree2strChild(t.right,sb);
sb.append(")");
}
}
}13. 二叉树的前序遍历
链接?144. 二叉树的前序遍历 - 力扣（LeetCode）
题目要求
?上代码
(1)遍历递归思路：在方法的外面new ，遇到合适的元素结点就给进放
class Solution {
List<Integer> ret = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return ret;
ret.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return ret;
}
}（2）子问题思路：将左边遍历完放进去，再遍历右边完放进去，也就是大问题变小问题
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null) return ret;
ret.add(root.val);
List<Integer> leftTree = preorderTraversal(root.left);
ret.addAll(leftTree);
List<Integer> rightTree = preorderTraversal(root.right);
ret.addAll(rightTree);
return ret;
}（3）方法三：用栈实现非递归前序遍历?
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || ! stack.empty()) {
while(cur != null) {
stack.push(cur);
ret.add(cur.val);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
return ret;
}
}14. 二叉树的中序遍历
链接?94. 二叉树的中序遍历 - 力扣（LeetCode）
题目要求
?上代码
(1)遍历递归思路：在方法的外面new ，遇到合适的元素结点就给进放
class Solution {
List<Integer> ret = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return ret;
inorderTraversal(root.left);
ret.add(root.val);
inorderTraversal(root.right);
return ret;
}
}?（2）子问题思路
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null) return ret;
List<Integer> leftTree = inorderTraversal(root.left);
ret.addAll(leftTree);
ret.add(root.val);
List<Integer> rightTree = inorderTraversal(root.right);
ret.addAll(rightTree);
return ret;
}
}?（3）方法三：用栈实现非递归后序遍历?
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null ) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.empty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
ret.add(top.val);
cur = top.right;
}
return ret;
}
}?
15. 二叉树的后序遍历
链接?145. 二叉树的后序遍历 - 力扣（LeetCode）
题目要求
?上代码
（1）子问题
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null) return ret;
List<Integer> leftTree = postorderTraversal(root.left);
ret.addAll(leftTree);
List<Integer> rightTree = postorderTraversal(root.right);
ret.addAll(rightTree);
ret.add(root.val);
return ret;
}
}（2）遍历递归
class Solution {
List<Integer> ret = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) return ret;
postorderTraversal(root.left);
postorderTraversal(root.right);
ret.add(root.val);
return ret;
}
}（3）方法三：用栈实现非递归后序遍历?
后序遍历和前序遍历不同的是
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null ) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;
TreeNode cur = root;
while(cur != null || !stack.empty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
//top.right 如果已经被访问了，也要弹出top所指向的结点
if(top.right == null || top.right == prev) {
stack.pop();
ret.add(top.val);
prev = top;
}else {
cur = top.right;
}
}
return ret;
}
}