1. 对称二叉树
思路：
- 在根的值一样接着往下判断
- 判断左树的左子树的值和右树的右子树的值是否相同
- 判断左树的右子树的值和右树的左子树的值是否相同
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) {
return true;
}
if ((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)) {
return false;
}
if (leftTree.val != rightTree.val) {
return false;
}
return isSymmetricChild(leftTree.left, rightTree.right) &&
isSymmetricChild(leftTree.right , rightTree.left);
}
2.二叉树的构建及遍历
要求：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
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 {
public static int i = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str = in.nextLine();
TreeNode root = createTree(str);
inorder(root);
}
}
public static TreeNode createTree(String str) {
//1.遍历字符串str
TreeNode 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);
}
}
3.二叉树的层序遍历
层序遍历：按照从上到下，从左到右的顺序来访问每一层的节点。
思路：**利用队列的先进先出的思想，先从根节点出发，将其压入队列中，接着判断从队列中弹出来的节点的左右孩子；若该节点的左孩子不为null时，将其压入队列。一直循环，当队列为空时，说明已经把该树遍历完了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
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> tmp = new ArrayList<>();
// 层序遍历
while (size != 0){
TreeNode cur = queue.poll();
//System.out.print(cur.val+" ");
tmp.add(cur.val);
size--;
if (cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
ret.add(tmp);
}
return ret;
}
void levelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 层序遍历
TreeNode cur = queue.poll();
System.out.print(cur.val+" ");
if (cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
4.给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
思路：root还是在遍历这棵树，遇到p或者q就返回
- 如果root节点是p或者是q 那么root是最近祖先
- 如果pq分布在root的左右两侧，那么root就是最近祖先
- pq在root的同一侧 遇到的第一个就是公共祖先，即左边不为空，右部为空 或者左空，右不空
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;
}
}
5. 二叉树创建字符串
思路：
- 根节点直接拼接
- 左边为空 && 右空 直接返回
- 左边不为空，右边为空，加“（”
- 左边为空，右边不为空 直接加一对括号“（）”
public String tree2str(TreeNode root) {
StringBuilder stringBuilder = new StringBuilder();
tree2strChild(root,stringBuilder);
return stringBuilder.toString();
}
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;
}
}
用栈来存放路径上的节点
public TreeNode lowestCommonAncestor2(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;
}
//判断左树没有这个节点 右树没有这个节点 那么当前的root就不是路径上的节点
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 flg = getPath(root.left,node,stack);
if(flg) {
return true;
}
boolean flg2 = getPath(root.right,node,stack);
if(flg2) {
return true;
}
stack.pop();
return false;
}