一 .接引二叉树(一)：承接上篇，不清楚的可以回去看看：二叉树基础及实现（一）-CSDN博客 1. 判断一棵树是不是完全二叉树： 图解： 把二叉树元素放入队列中，如果最后队列里全部是元素，“null”，则该二叉树就是完全二叉树。 这里注意区分，空和元素,“null”的概念
代码：
代码语言：javascript复制 //判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
//空节点也是完全二叉树
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
//空节点也放进去
if (cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()) {
TreeNode peek = queue.peek();
//注意这里的null，是队列里的元素是“null”，不是队列为空
if (peek != null) {
return false;
}
//可以全部弹完，说明队列里就只有 null 元素.就是完全二叉树
queue.poll();
}
return true;
}二 .二叉树相关oj题： 1. 检查两颗树是否相同：
题目：
图解：
代码：
代码语言：javascript复制 public boolean isSameTree(TreeNode p, TreeNode q) {
//先判断结构是否一样
if(p != null && q == null || q != null && p == null) {
return false;
}
//走到这里，两个都为空或者两个都不为空
//排除都为空树，但是空树也是树
if(p == null && q == null) {
return true;
}
//走到这里两个都不为空
//开始判断树，根的值是否一样
if(p.val != q.val) {
return false;
}
//树都不为空，树根的值一样就判断：左子树 && 右边是否一样
if(isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right)) {
return true;
}
return false;
}2. 另一颗树的子树：
题目：
图解：
代码：
代码语言：javascript复制 public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//这里是递归遍历root的返回条件，不能省略，我们要在root这颗大树上遍历找subRoot树
if(root == null) {
return false;
}
//判断整个树的根只有一次，就用isSameTree
if(isSameTree(subRoot, root)) return true;
//来到第二层，这里要递归遍历root，
//因为这棵树可能包含subRoot的子树
if(isSubtree(root.left,subRoot)) return true;//root的左树
if(isSubtree(root.right,subRoot)) return true;//root的右树
return false;
}
//判断两棵树是否相同
public boolean isSameTree(TreeNode p, TreeNode q) {
//先= null) {
return true;
}
//走到这里两个都不为空
//开始判断树，根的值是否一样
if(p.val != q.val) {
return false;
}
//树都不为空，树根的值一样就判断：左子树 && 右边是否一样
if(isSameTree(p.left, q.left)
&& isSameTree(p.right判断结构是否一样
if(p != null && q == null || q != null && p == null) {
return false;
}
//走到这里，两个都为空或者两个都不为空
//排除都为空树，但是空树也是树
if(p == null && q =, q.right)) {
return true;
}
return false;
}3. 翻转二叉树：
题目：
图解：
代码：
代码语言：javascript复制 public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
//递归前序遍历
invertTree(root.left);
invertTree(root.right);
return root;
}4. 判断一颗二叉树是否是平衡二叉树：
题目：
方法一：时间复杂度为O（N^2,N的平方）；因为我们求高度自己实现的函数getHeight，是先遍历到，最后一个二叉树再逐一返回，当（isBalanced(root.left) && isBalanced(root.right)，去递归每一棵树的左右子树）时会重复去算高度。
图解：
代码：
代码语言：javascript复制时间复杂度为O（N^2,N的平方）；因为我们求高度自己实现的函数getHeight，是先遍历放到
最后一次二叉树再，逐一返回，当（isBalanced(root.left) && isBalanced(root.right);//去递归每一棵树的左右子树）时会重复去算高度
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
//判断二叉树节点是平衡树
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.abs(leftHeight - rightHeight) < 2 &&
isBalanced(root.left) && isBalanced(root.right);//去递归每一棵树的左右子树
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
//递归遍历左右树高度，遍历到root == null，再返回
int leftTreeHeight = getHeight(root.left);
int rightTreeHeight = getHeight(root.right);
return Math.max(leftTreeHeight, rightTreeHeight) 1;
}
}解法二：时间复杂度为O(N)： 方法 : 返回时，顺便判断属不属于平衡二叉树，不属于返回-1，属于返回高度
代码；
代码语言：javascript复制 public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
//返回的高度 >= 0则是平衡二叉树
return getHeight(root) >= 0;
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
//递归遍历左右树高度，遍历到root == null，再返回
int leftTreeHeight = getHeight(root.left);
if(leftTreeHeight < 0) {
return -1;
}
int rightTreeHeight = getHeight(root.right);
/**
这里注意当二叉树遍历整棵树的最右边时，右边会返回-1，会破坏右边二叉树返回时的高度
所以，rightTreeHeight的值要判断；如果等于-1，就不可以向上返回
限制：（rightTreeHeight>=0）
*/
if(rightTreeHeight>=0 && Math.abs(leftTreeHeight-rightTreeHeight) <= 1){
//是平衡二叉树,返回左右树做大值加1
return Math.max(leftTreeHeight, rightTreeHeight) 1;
}else {
return -1;
}
}
5. 对称二叉树：
题目
图解：
代码：
代码语言：javascript复制public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
//封装起来判断，每个树的左右子树是否对称
public boolean isSymmetric(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;
}
//开始判断对称,现在leftTree和rightTree都作为根
return isSymmetric(leftTree.left,rightTree.right) &&
isSymmetric(leftTree.right,rightTree.left);
}6. 二叉树的构建及遍历：
题目：
图解：
代码：
代码语言：javascript复制import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = createTree(str);
inorderTree(root);
}
}
//创建二叉树：
//遍历字符串的全局变量，局部变量递归时会把i置0
public static int i = 0;
public static TreeNode createTree(String str) {
TreeNode root = null;
if(str.charAt(i) != '#') {
//先创建一个根节点
root = new TreeNode(str.charAt(i));
//创建好，i往后走，创建左右子树的各个节点
i ;
root.left = createTree(str);
root.right = createTree(str);
}else {
i ;
}
return root;
}
//中序遍历打印二叉树
public static void inorderTree(TreeNode root) {
if(root == null) {
return;
}
inorderTree(root.left);
System.out.print(root.val " ");
inorderTree(root.right);
}
}
7. 二叉树的分层遍历 ：
题目：
图解：
代码：
代码语言：javascript复制 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()) {
List<Integer> list = new ArrayList<>();
//定义放在这里，等二叉树走完一层，才更新另外一层的size
int size = queue.size();
while(size != 0) {
TreeNode cur = queue.poll();
list.add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
size--;
}
//一维数组走完一个放入二维数组一个
ret.add(list);
}
return ret;
}
8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先：
题目：
图解：解法一：
代码：
代码语言：javascript复制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 && rightTree == null) {
return leftTree;
}else {
return rightTree;
}
}图解2：方法二：通过两个栈解决：
代码：
代码语言：javascript复制 //最近公共祖先,方法二 ：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> stackP = new Stack<>();
Stack<TreeNode> stackQ = new Stack<>();
//1.把元素存入栈中
getPath(root, p,stackP);
getPath(root, q,stackQ);
//2.求出那个栈元素多，让多的先出栈，直到两个栈元素一样多
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()) {
//stackP == stackQ，比较节点，如果比较的值是Integer类型,超过一定范围就要无效，要用equals比较
if ( stackQ.peek() == stackP.peek()) {
return stackP.peek();
}else {
//元素不一样就出栈
stackP.pop();
stackQ.pop();
}
}
return null;
}
/**
*
* @param root
* @param node:要找路径的q p 节点
* @param stack:存放节点的栈
*/
//获取q, p路径
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if (root == null) {
return false;
}
//节点放入栈中
stack.push(root);
//找到返回true
if (root == node) {
return true;
}
//递归找q, p, 递归返回值ret
boolean ret = getPath(root.left,node,stack);
//一层一层往上走
if (ret) {
return true;
}
ret = getPath(root.right,node,stack);
if (ret) {
return true;
}
//左右树遍历完没有找到,就把不是该路径的，节点弹出栈，并返回false
stack.pop();
return false;
}9. 根据一棵树的前序遍历与中序遍历构造二叉树：
题目：
图解：
代码：
代码语言：javascript复制 public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder, inorder,0,inorder.length-1);
}
public int preIndex;
public TreeNode buildTreeChild(int[] preorder , int[] inorder,int inbegin, int inend) {
//没有左树或者右树
if(inbegin > inend) {
return null;
}
//new一个根节点
TreeNode root = new TreeNode(preorder[preIndex]);
//在中序遍历中从，前序遍历那里找到，代表所有子树的 根节点
int rootIndex = findVal(inorder,inbegin,inend, preorder[preIndex]);
//preIndex，要改为全局变量，左右每次递归是，才不会重置为0
preIndex ;//rootInde用完才加加；
//递归每一个创建左右子树
root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
root.right = buildTreeChild(preorder,inorder,rootIndex 1,inend);
return root;
}
private int findVal(int[] inorder,int inbegin, int inend,int val) {
for(int i = inbegin; i<=inend; i ) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}10. 根据一棵树的中序遍历与后序遍历构造二叉树：
题目：
图解：
代码：
代码语言：javascript复制 public TreeNode buildTree(int[] inorder, int[] postorder) {
postorIndex = postorder.length-1;
return buildTreeChild(inorder, postorder,0,inorder.length-1);
}
public int postorIndex;
public TreeNode buildTreeChild(int[] inorder , int[] postorder,int inbegin, int inend) {
//没有左树或者右树
if(inbegin > inend) {
return null;
}
//new一个根节点
TreeNode root = new TreeNode(postorder[postorIndex]);
//在中序遍历中从，前序遍历那里找到，代表所有子树的 根节点
int rootIndex = findVal(inorder,inbegin,inend, postorder[postorIndex]);
//preIndex，要改为全局变量，左右每次递归是，才不会重置为0
postorIndex--;//rootInde用完才；
//递归每一个创建左右子树
root.right = buildTreeChild(inorder,postorder,rootIndex 1,inend);
root.left = buildTreeChild(inorder,postorder,inbegin,rootIndex-1);
return root;
}
private int findVal(int[] inorder,int inbegin, int inend,int val) {
for(int i = inbegin; i<=inend; i ) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}11. 二叉树创建字符串：
题目：
图解：
代码：
代码语言：javascript复制 public String tree2str(TreeNode root) {
if(root == null) {
return null;
}
StringBuilder stringbuilder = new StringBuilder();
tree2strChild(root, stringbuilder);
return stringbuilder.toString();
}
public void tree2strChild(TreeNode t, StringBuilder stringbuilder) {
if(t == null) {
return;
}
//先拼接根节点
stringbuilder.append(t.val);
if(t.left != null) {
stringbuilder = stringbuilder.append("(");
tree2strChild(t.left, stringbuilder);//递归拼接左边
//每一颗子树走完，就拼接“）”
stringbuilder.append(")");
}else {
if(t.right == null) {
//左右都为空
return;
}else {
//左边为空，右边不为空就拼接 “（）”。
stringbuilder.append("()");
}
}
if(t.right != null) {
stringbuilder = stringbuilder.append("(");
tree2strChild(t.right, stringbuilder);//递归拼接右边
//每一颗子树走完，就拼接“）”
stringbuilder.append(")");
}else {
//右边为空
return;
}
}12. 二叉树前序非递归遍历实现 ：
图解：这里用到栈
代码：
代码语言：javascript复制 // 方法二：
List<Integer> list = new LinkedList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
//根节点开始要放入栈中
cur = stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
//cur == null，就把栈里的元素，拿到top引用中
TreeNode top = stack.pop();
//cur再走top的右边
cur = top.right;
}
return list;13. 二叉树中序非递归遍历实现： 这里和上面方法一样，只是在出栈时候，放入链表或者顺序表，又或者打印。
代码：
代码语言：javascript复制public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {
return list;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
cur = stack.push(cur);
cur = cur.left;
}
//cur == null，就把栈里的元素，拿到top引用中
TreeNode top = stack.pop();
list.add(top.val);
//cur再走top的右边
cur = top.right;
}
return list;
}14. 二叉树后序非递归遍历实现： 这里思路也是大同小异，但是这里要定义一个，prev引用，记录一下被打印过的节点，左右cur就不会一直在，top的右边死循环了
图解：
代码：
代码语言：javascript复制public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
//结束条件
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
//prev负责记录已经被放入list (被打印过) 的结点
TreeNode prev = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if (top.right == null || top.right == prev) {
list.add(top.val);
stack.pop();
prev = top;//prev负责记录被打印过的结点
}else {
cur = top.right;
}
}
return list;
}
