二叉树相关oj题(Java)

一. 检查两颗树是否相同。OJ链接

这里我们考虑两种情况:

1.结构上

2.节点值上 

当上面两种情况同时遍历时:

1.如果两颗树的节点都不为空,就判断值

2.如果两棵树种一棵树的节点为空另一棵树的节点不为空,则这两颗肯定不是相同的树

整体来看:要判断两棵树是否相同,得判断根,然后判断两棵树的左子树是否相同&&两棵树的右子树是否相同,只有满足这两种情况,两棵树才相同

代码如下:

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);}

结果如下:

二. 另一颗树的子树。OJ链接

 

看上图,如果是子树的话有可能是两棵相同的树,这里如果根节点比较完,不是两棵相同的树,那是不是意味着,这个subRoot这棵树和root的某一个子树是相同的,所以这里就意味着判断的是subRoot和root的左树是不是相同的,如果不是那么就判断右树

(这里就会使用到上题1中判断两棵树是否相同的那个代码 isSameTree())

代码如下: 

  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;}return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null || subRoot == null) {return false;}//1、是不是和根节点相同if(isSameTree(root,subRoot)) {return true;}//2、判断是不是root的左子树if(isSubtree(root.left,subRoot)) {return true;}//3、右子树if(isSubtree(root.right,subRoot)) {return true;}//4、返回return false;}

提交结果:

三. 翻转二叉树。OJ链接

思维图:

public TreeNode invertTree(TreeNode root) {if(root == null) {return null;}if(root.left == null && root.right == null) {return root;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}

结果如下:

四. 判断一颗二叉树是否是平衡二叉树。OJ链接

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。

平衡二叉树的意思就是:如上图:我们不仅仅只判断3的左右高度差小于等于1,还要判断9的左右高度差小于等于1,还有20的左右高度差小于等于1,还有15和7的左右高度差小于等于1

(这里我们就要求每个节点的左树和右树的高度

其次判断根的左树是平衡的&&右树也是平衡的&&看当前根节点的左树-右树的绝对值是否<=1)

这里我们就要用到上篇说到的求树的高度这个方法

代码如下: 

 //最坏情况下 每个节点 都要求高度
//时间复杂度：O(N^2)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);}public int maxDepth(TreeNode root) {if(root == null) {return 0;}int leftHeight =  maxDepth(root.left);int rightHeight =  maxDepth(root.right);return leftHeight > rightHeight ? leftHeight+1:rightHeight+1;}//上面的代码重复的高度计算太多了,下面代码是优化代码,此时是一边求高度一边判断平衡问题//O(n)的时间复杂度(32.34)class Solution {public boolean isBalanced(TreeNode root) {if(root == null) {return true;}return maxDepth(root) >= 0;}public int maxDepth(TreeNode root) {if(root == null) {return 0;}int leftHeight =  maxDepth(root.left);if(leftHeight < 0) {return -1;}int rightHeight =  maxDepth(root.right);if(leftHeight >= 0 && rightHeight >= 0&& Math.abs(leftHeight-rightHeight) <= 1) {//在这种情况下 我才会返回 真实的高度return Math.max(leftHeight,rightHeight)+1;}else {return -1;}}}

结果如下:

五.二叉树的最大深度.OJ链接 

代码如下:

class Solution {public int maxDepth(TreeNode root) {if(root==null){return 0;}int leftHeight=maxDepth(root.left);int rightHeight=maxDepth(root.right);return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}
}

 结果如下:

六. 对称二叉树。OJ链接

这里要判断root的左树和root的右树是不是对称的.

分为以下情况:

1.

一就是一个为空一个不为空的情况下,他一定是不对称的.

2.

而就是值不一样不对称

3.

如上这种情况第一幅图是对称的.

第二幅图判断左树和右树是否对称,就要判断:

1.根得值是否一样

2.左树的左和右树的右是否一样

3.左树的右和右树的左是否一样

代码如下:

 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 ||leftTree == null && rightTree != 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);}
}

 结果如下:

七. 二叉树的构建及遍历。OJ链接

代码如下:(9.26.1.42.45)

import java.util.Scanner;class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {//被static修饰的成员变量,只有一份,他和很多对象共享,本题只有一个测试用例,所有不会报错public static int i = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();TreeNode root = createTree(str);inorder(root);}}public static TreeNode createTree(String str) {//1. 遍历字符串strTreeNode root = null;if(str.charAt(i) != '#') {//2. 根据前序遍历创建二叉树root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);}else {i++;}//3.返回根节点return root;}public static void inorder(TreeNode root) {if(root == null) {return ;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}}

结果如下:

八. 二叉树的分层遍历 。OJ链接

 

这里的难点问题是我们怎么确定每层有几个节点呢?还有就是怎么存储每一层的节点到list当中.

和上一篇中的层序遍历一样,都要用到队列.(原理一模一样,都定义一个队列和一个cur)

以上图为例,这里还是先把A放进队列,然后树不为空,出A,所以他是第一层,有一个节点,再把A的左树和右树放进去,此时队列里面有2个元素,就是第二层,这里是两个元素,出两次就好了,也意味着出B的时候把D和E带进队列了,再出C就把F和G带进队列了,这是刚好B和C加起来出了两次,说明第二层有两个节点,此时队列里面有四个元素,就是第三层,后面依次类推

代码如下:

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);//Awhile (!queue.isEmpty()) {int size = queue.size();//1List<Integer> tmp = new ArrayList<>();while (size != 0) {TreeNode cur = queue.poll();//System.out.print(cur.val + " ");tmp.add(cur.val);size--;//0if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}ret.add(tmp);}return ret;}
}

结果如下:

九 .给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接

 思维图如下:

注意:其中第三种情况,p和q在root的一侧这种情况,只需要找到p或者q中的一个就返回,不用再找另一个.

代码如下:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) 
return null;if(root == p || root == q) {return root;}TreeNode leftTree = lowestCommonAncestor(root.left,p,q);TreeNode rightTree = lowestCommonAncestor(root.right,p,q);if(leftTree != null && rightTree != null) {return root;}else if(leftTree != null) {//如果左不为空return leftTree;}else {//如果右不为空return rightTree;}}

代码结果如下:

这里再给大家说一个比较好理解的写法:

上面的节点只是保存了左右孩子,这里我们让节点再保存他父亲的节点,而这个就相当于在求链表的交点 

但是这里的问题是二叉树本身没有包含他的父亲节点,那该怎么做呢?

很简单如上图,这里我们申请两个栈,第一个栈里面放从根到p这条路径上的所有节点,第二个栈里面放从根到q这条路径上的所有节点.第二个栈比第一个栈大,就让第二个栈先出一个节点4,然后两个栈同时出,第一个栈出了个6,第二个栈出了个2,两个节点不相同,继续出,第一个栈出了个5,第二个栈出了个5,相同,则他的最近祖先是节点5.

但是这里的问题是如何存储一条路径上,从根节点到p或者q的路径上的所有节点?

这里我们给一个方法getpath(root,p),它包含根节点和一个节点p或者q节点,这里我们要有通过这个方法,然后拿到root到p或者q这个路径上的所有节点.

还有一个问题是一个节点是不是这条路径上的?

也很简单,只要判断,左树没有这个节点,右树也没有这个节点(没有这个节点就是返回null或者返回false/ture),那么当前的root就不是路径上的节点

以上图为例. 

思维图:

代码如下: 

class Solution{public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;Stack<TreeNode> stackP = new Stack<>();Stack<TreeNode> stackQ = new Stack<>();getPath(root,p,stackP);getPath(root,q,stackQ);int sizeP = stackP.size();int sizeQ = stackQ.size();if(sizeP > sizeQ) {int size = sizeP - sizeQ;while(size != 0) {stackP.pop();size--;}}else {int size = sizeQ - sizeP;while(size != 0) {stackQ.pop();size--;}}//两个栈当中的元素是一样多while(!stackP.isEmpty() && !stackQ.isEmpty()) {if(stackP.peek() == stackQ.peek()) {return stackP.peek();}else{stackP.pop();stackQ.pop();}}return null;}private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {//Stack<TreeNode> stack指吧TreeNode放到栈里面if(root == null || node == null) {return false;}stack.push(root);if(root == node) {return true;}boolean flg = getPath(root.left,node,stack);//左边找node,元素最后都放到stack里面if(flg==true) {return true;}boolean flg2 = getPath(root.right,node,stack);//右边找node,元素最后都放到stack里面if(flg2==true) {return true;}stack.pop();//6的左树和右树都没有节点,弹出栈return false;}
}

结果如下:

十. 根据一棵树的前序遍历与中序遍历构造二叉树。OJ链接

思维图如下:

定义一个i,遍历前序遍历 ,从根节点开始遍历,然后对应的在中序遍历中找到根节点(E是根节点,根节点的左边是左树,根节点的右边是右树,如上中序遍历图划分)

代码如下:

class Solution {public int preIndex ;//成员变量public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChilde(preorder,inorder,0,inorder.length-1);}private TreeNode buildTreeChilde(int[] preorder,int[] inorder,int inbegin,int inend) {if(inbegin > inend) {return null;//没有 左树 或者 没有 右树 }TreeNode root = new TreeNode(preorder[preIndex]);int rootIndex = findIndexRoot(inorder,inbegin,inend,preorder[preIndex]);if(rootIndex == -1) {return null;}preIndex++;root.left = buildTreeChilde(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChilde(preorder,inorder,rootIndex+1,inend);return root;}private int findIndexRoot(int[] inorder,int inbegin, int inend,int key) {for(int i = inbegin; i <= inend;i++) {if(inorder[i] == key) {return i;}}return -1;}
}

结果如下:

10.根据一棵树的中序遍历与后序遍历构造二叉树（[课堂不讲解，课后完成作业]）。OJ链接

这个和上面有一个不一样的点是,后序遍历从最后一个节点开始,然后减减,然后中序遍历中先创建右树(因为后序遍历是左右根) 

代码如下: 

class Solution {public int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length-1;return buildTreeChilde(postorder,inorder,0,inorder.length-1);}private TreeNode buildTreeChilde(int[] postorder,int[] inorder,int inbegin,int inend) {if(inbegin > inend) {return null;//没有 左树 或者 没有 右树 }TreeNode root = new TreeNode(postorder[postIndex]);int rootIndex = findIndexRoot(inorder,inbegin,inend,postorder[postIndex]);if(rootIndex == -1) {return null;}postIndex--;root.right = buildTreeChilde(postorder,inorder,rootIndex+1,inend);root.left = buildTreeChilde(postorder,inorder,inbegin,rootIndex-1);return root;}private int findIndexRoot(int[] inorder,int inbegin, int inend,int key) {for(int i = inbegin; i <= inend;i++) {if(inorder[i] == key) {return i;}}return -1;}
}

 结果如下:

11. 二叉树创建字符串。OJ链接

先来看第一幅图,根据解释和输出,我们可以得到点:

1.根节点直接拼接

2.左边为空&&右边为空的时候什么都不做

3.左边不为空右边为为空也什么都没有做

 这幅图和上面一样,根据解释和输出,我们可以得到点:

1.左边为空右边不为空 直接加一对括号

根据上面两个例子得出的大方向是:要采用前序遍历的方式进行遍历 

代码如下:

class Solution {public String tree2str(TreeNode root) {StringBuilder stringBuilder = new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();//stringBuilder转String}private void tree2strChild(TreeNode t,StringBuilder stringBuilder) {if(t == null) {return ;}stringBuilder.append(t.val);if(t.left != null) {stringBuilder.append("(");tree2strChild(t.left,stringBuilder);stringBuilder.append(")");}else {if(t.right == null) {return;}else {stringBuilder.append("()");}}//判断右树if(t.right != null) {stringBuilder.append("(");tree2strChild(t.right,stringBuilder);stringBuilder.append(")");}else {return;}}
}

 结果如下:

12. 二叉树前序非递归遍历实现 。OJ链接

非递归怎么遍历呢?

很简单,这里用栈.这里就是往栈里面放一个打印一个

代码如下:

//IDEA上的代码实现void preOrderNor(TreeNode root){if(root==null){return;}Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while(cur!=null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.println(cur.val + " ");cur = cur.left;}TreeNode top=stack.pop();cur=top.right;}}

13. 二叉树中序非递归遍历实现。OJ链接

14. 二叉树后序非递归遍历实现。OJ链接