- 习题一： 求一棵树的左视图
代码：
public List leftMap(Node root) {
List ret=new ArrayList<>();
if(root==null){
return ret;
}
Queue queue =new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
int count=size;
while(size>0){
Node top=queue.poll();
if(count==size){
ret.add(top.val);
}
if(top.left!=null){
queue.offer(top.left);
}
if(top.right!=null){
queue.offer(top.right);
}
size–;
}
}
return ret;
}
- 习题二： 求二叉树的最大宽度
代码：
public int maxWidth(Node root) {
if(root==null){
return 0;
}
Queue queue =new LinkedList<>();
queue.offer(root);
int max=0;
while(!queue.isEmpty()){
int size=queue.size();
max=Math.max(max,size);
while(size>0){
Node top=queue.poll();
if(top.left!=null){
queue.offer(top.left);
}
if(top.right!=null){
queue.offer(top.right);
}
size–;
}
}
return max;
}
- 习题三： 判断一棵树是不是完全二叉树
代码：
public boolean isCompleteTree(Node root){
if(root==null){
return true;
}
Queue queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node top=queue.poll();
if(top==null){
break;
}
queue.offer(top.left);
queue.offer(top.right);
}
while(!queue.isEmpty()){
Node top=queue.peek();
if(top!=null){
return false;
}
queue.poll();
}
return true;
}
2.6.2 二叉树的实现由于二叉树的创建一般使用递归，而递归创建二叉树将在后面重点介绍。故这里使用穷举法来创建下面这棵二叉树
实现代码：
class Node{
public char val;
public Node left;
public Node right;
public Node(char val){
this.val=val;
}
}
public class TestBinaryTree {
// 使用穷举的方式创建一棵二叉树
public Node createTree(){
Node A=new Node(‘A’);
Node B=new Node(‘B’);
Node C=new Node(‘C’);
Node D=new Node(‘D’);
Node E=new Node(‘E’);
Node F=new Node(‘F’);
Node G=new Node(‘G’);
Node H=new Node(‘H’);
A.left=B;
A.right=C;
B.left=D;
B.right=E;
E.right=H;
C.left=F;
C.right=G;
return A;
}
// 前序遍历
public void preOrderTraversal(Node root){
if(root==null) {
return;
}
System.out.print(root.val+" ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
// 中序遍历
public void inOrderTraversal(Node root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.val+" ");
inOrderTraversal(root.right);
}
// 后序遍历
public void posOrderTraversal(Node root){
if(root==null){
return;
}
posOrderTraversal(root.left);
posOrderTraversal(root.right);
System.out.print(root.val+" ");
}
// 遍历思路-求节点个数
public static int size=0;
public void getSize1(Node root){
if(root==null){
return;
}
size++;
getSize1(root.left);
getSize1(root.right);
}
// 子问题思路-求节点个数
public int getSize2(Node root){
if(root==null){
return size;
}
int val=1+getSize2(root.left)+getSize2(root.right);
return val;
}
// 遍历思路-求叶子节点个数
public static int leafSize;
public void getLeafSize1(Node root){
if(root==null){
return;
}
if(root.leftnull&&root.rightnull){
leafSize++;
return;
}
getLeafSize1(root.left);
getLeafSize1(root.right);
}
// 子问题思路-求叶子节点个数
public int getLeafSize2(Node root){
if(root==null){
return 0;
}
if(root.leftnull&&root.rightnull) {
return 1;
}
int val=getLeafSize2(root.left)+getLeafSize2(root.right);
return val;
}
// 第 k 层的节点个数
public int getKLeafSize(Node root,int k){
if(root==null){
return 0;
}
if(k==1){
return 1;
}
int val=getKLeafSize(root.left,k-1)+getKLeafSize(root.right, k-1);
return val;
}
// 获取当前二叉树的高度
public int getHeight(Node root){
if(root==null){
return 0;
}
return 1+Math.max(getHeight(root.left),getHeight(root.right));
}
// 查找二叉树的某个节点
public Node find(Node root,char val){
if(root==null){
return null;
}
if(root.val==val){
return root;
}
Node leftNode=find(root.left,val);
if(leftNode.val==val){
return leftNode;
}
Node rightNode=find(root.right,val);
if(rightNode.val==val){
return rightNode;
}
return null;
}
}
2.7 前中后序的非递归实现
递归的实现都是在栈上进行的，如果我们要用非递归的方式实现一棵二叉树，那么我们的核心思想就是创建一个栈，并在这个栈上模拟递归。
- 前序遍历非递归实现
代码示例：
public void preOrderTraversal(Node root){
if(root==null){
return;
}
Stack stack=new Stack<>();
Node cur=root;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
System.out.print(cur.val+" ");
cur=cur.left;
}
Node top=stack.pop();
cur=top.right;
}
}
- 中序遍历非递归实现
代码示例：
public void inOrderTraversal(Node root){
if(root==null){
return;
}
Stack stack=new Stack<>();
Node cur=root;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
cur=cur.left
}
Node top=stack.pop();
System.out.print(top.val+" ");
cur=top.right;
}
}
- 后序遍历非递归实现
代码示例：
public void posOrderTraversal(Node root){
if(root==null){
return;
}
Node prev=null;
Stack stack=new Stack<>();
Node cur=root;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
Node top=stack.peek();
cur=top.right;
if(curnull||cur.valprev.val){
System.out.print(top.val+" ");
prev=stack.pop();
cur=null;
}
}
}
3. 二叉树练习题
=============================================================================
3.1 二叉树基础练习题
3.1.1 二叉树的前序遍历
题目（OJ 链接）：
给你二叉树的根节点 root ，返回它节点值的前序遍历。
代码一： 子问题的思路：将左子树、右子树和根都存放进去
public List preorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
list.add(root.val);
List leftTree=preorderTraversal(root.left);
list.addAll(leftTree);
List rightTree=preorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
代码二： 遍历思路：将每个节点都遍历一遍
List list=new ArrayList<>();
public List preorderTraversal(TreeNode root) {
if(root==null){
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
3.1.2 二叉树的中序遍历题目（OJ 链接）：
给定一个二叉树的根节点 root ，返回它的中序遍历。
代码一： 子问题思路
public List inorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
List leftTree=inorderTraversal(root.left);
list.addAll(leftTree);
list.add(root.val);
List rightTree=inorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
代码二： 遍历思路
List list=new ArrayList<>();
public List inorderTraversal(TreeNode root) {
if(root==null){
return list;
}
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
return list;
}
3.1.3 二叉树的后序遍历题目（OJ 链接）：
给定一个二叉树，返回它的后序遍历。
代码一： 子问题思
public List postorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
List leftTree=postorderTraversal(root.left);
list.addAll(leftTree);
List rightTree=postorderTraversal(root.right);
list.addAll(rightTree);
list.add(root.val);
return list;
}
代码二： 遍历思路
List list=new ArrayList<>();
public List postorderTraversal(TreeNode root) {
if(root==null){
return list;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
list.add(root.val);
return list;
}
3.1.4 相同的树题目（OJ 链接）：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
代码：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p!=null&&qnull||pnull&&q!=null){
return false;
}
if(pnull&&qnull){
return true;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
3.1.5 另一棵树的子树题目（OJ 链接）：
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
代码：
class Solution {
public boolean isSameTree(TreeNode root,TreeNode subRoot){
if(root!=null&&subRootnull||rootnull&&subRoot!=null){
return false;
}
if(rootnull&&subRootnull){
return true;
}
if(root.val!=subRoot.val){
return false;
}
return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.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.1.6 二叉树的最大深度题目（OJ 链接）：
给定一个二叉树，找出其最大深度。
代码：
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
3.1.7 平衡二叉树题目（OJ 链接）：
给定一个二叉树，判断它是否是高度平衡的二叉树。
代码一： 时间复杂度为 O(N2)
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int leftDepth=maxDepth(root.left);
int rightDepth=maxDepth(root.right);
if(Math.abs(leftDepth-rightDepth)>1){
return false;
}
return isBalanced(root.left)&&isBalanced(root.right);
}
}
代码二： 时间复杂度为 O(N)
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int leftDepth=maxDepth(root.left);
int rightDepth=maxDepth(root.right);
if(leftDepth>=0&&rightDepth>=0&&Math.abs(leftDepth-rightDepth)<=1){
return 1+Math.max(leftDepth,rightDepth);
}else{
return -1;
}
}
public boolean isBalanced(TreeNode root) {
return maxDepth(root)>=0;
}
}
3.1.8 对称二叉树题目（OJ 链接）：
给定一个二叉树，检查它是否是镜像对称的。
代码：
class Solution {
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
if(leftTreenull&&rightTreenull){
return true;
}
if(leftTree!=null&&rightTreenull||leftTreenull&&rightTree!=null){
return false;
}
if(leftTree.val!=rightTree.val){
return false;
}
return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
}
public boolean isSymmetric(TreeNode root) {
if(root==null){
return false;
}
return isSymmetricChild(root.left,root.right);
}
}
3.2 二叉树进阶练习题
3.2.1 二叉树的构建及遍历
题目（OJ 链接）：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
代码：
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
public class Main{
public static int i=0;
publ
《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》
【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享
ic static TreeNode createBinaryTree(String str){
if(str.length()==0){
return null;
}
TreeNode root=null;
if(str.charAt(i)==’#’){
i++;
}else{
root=new TreeNode(str.charAt(i));
i++;
root.left=createBinaryTree(str);
root.right=createBinaryTree(str);
}
return root;
}
public static void inOrderTraversal(TreeNode root){
if(root==null){
return;
}
inOrderTraversal(root.left);
System.out.print(root.val+" ");
inOrderTraversal(root.right);
}
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
while(scan.hasNext()){
String str=scan.nextLine();
TreeNode ret=createBinaryTree(str);
inOrderTraversal(ret);
System.out.println();
}
}
}
3.2.2 二叉树的层序遍历题目（OJ 链接）：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
代码：
class Solution {
public List levelOrder(TreeNode root) {
List ret=new ArrayList<>();
if(root==null){
return ret;
}
Queue queue =new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
List list=new ArrayList<>();
while(size>0){
TreeNode top=queue.poll();
list.add(top.val);
if(top.left!=null){
queue.offer(top.left);
}
if(top.right!=null){
queue.offer(top.right);
}
size–;
}
ret.add(list);
}
return ret;
}
}
3.2.3 二叉树的最近公共祖先题目（OJ 链接）：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(rootp||rootq){
return root;
}
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left!=null&&right==null){
return left;
}
if(left==null&&right!=null){
return right;
}
if(leftnull&&rightnull){
return null;
}
return root;
}
}
3.2.4 二叉搜索树与双向链表题目（OJ 链接）：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
代码：
public class Solution {
public TreeNode prev;
public void ConvertChild(TreeNode pCur) {
if(pCur==null){
return;
}
ConvertChild(pCur.left);
pCur.left=prev;
if(prev!=null){
prev.right=pCur;
}
prev=pCur;
ConvertChild(pCur.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;
}
}
补充：
3.2.5 从前序与中序遍历序列构造二叉树二叉搜索树特点： 左孩子比根节点小，右孩子比根节点大
题目（OJ 链接）：
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
代码：
class Solution {
public int prevIndex=0;
public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
if(inBegin>inEnd){
return null;
}
TreeNode root=new TreeNode(preorder[prevIndex]);
int index=findIndex(inorder,inBegin,inEnd,root.val);
prevIndex++;
root.left=buildTreeChild(preorder,inorder,inBegin,index-1);
root.right=buildTreeChild(preorder,inorder,index+1,inEnd);
return root;
}
public int findIndex(int[] inorder,int inBegin,int inEnd,int k){
for(int i=inBegin;i<=inEnd;i++){
if(k==inorder[i]){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preordernull||inordernull){
return null;
}
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
}
