# 刷题---二叉树--2

## 平衡二叉树

``````int getHeight(TreeNode root){
if(root==null){
return 0;
}
int lightLeft=getHeight(root.left);
int lightRight=getHeight(root.right);
return lightLeft>lightRight?lightLeft+1:lightRight+1;
}
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int left=getHeight(root.left);
int right=getHeight(root.right);
if(Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right)){
return true;
}
return false;
}
``````

``````private int getHeight1(TreeNode root){
if(root==null){
return 0;
}
int lightLeft=getHeight(root.left);
int lightRight=getHeight(root.right);
if(lightLeft>=0 && lightRight>=0 && Math.abs(lightLeft- lightRight)<=1){
return Math.max(lightLeft,lightRight)+1;
}else{
return -1;
}
}
public boolean isBalanced1(TreeNode root) {
if(root==null){
return true;
}
return getHeight1(root)>=0;
}
``````

## 对称二叉树

`````` public boolean isSymmetricChild(TreeNode rightTree,TreeNode leftTree){
if(leftTree==null && rightTree!=null)  return false;
if(leftTree!=null && rightTree==null)  return false;
if(leftTree==null && rightTree==null)   return true;
if(rightTree.val!=leftTree.val){
return false;
}
return isSymmetricChild(leftTree.left,rightTree.right)&&
isSymmetricChild(leftTree.right,rightTree.left);
}
public boolean isSymmetric(TreeNode root) {
if(root==null)  return true;
return isSymmetricChild(root.left,root.right);
}
``````

## 二叉树遍历

``````import java.util.*;
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 ;
public static TreeNode createTree(String str) {
TreeNode root = null;
if(str.charAt(i) != '#') {
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
}else {
//遇到# 就是空树
i++;
}
return root;
}

public static 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 in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意多个输入
String str = in.nextLine();
TreeNode root = createTree(str);
inorder(root);
}
}
}
``````

## 二叉树的最近公共祖先

``````   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(p==root || q==root){
return root;
}
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left!=null && right!=null){
return root;
}else if(left==null && right!=null){
return right;
}else if(left!=null && right==null){
return left;
}
return null;
}
``````

``````public 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 flg1=getPath(root.right,node,stack);
if(flg1){
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==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>0){
int size=size1-size2;
while(size!=0){
stack1.pop();
size--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()){
if(stack1.peek()==stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}
}
}else{
int size=size2-size1;
while(size!=0){
stack2.pop();
size--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()){
if(stack1.peek()==stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}
}
}
return null;
}
``````

## 二叉搜索树与双向链表

``````    TreeNode pre=null;
public void inorder (TreeNode root){
if(root==null) return;
inorder(root.left);
root.left=pre;
if(pre!=null){
pre.right=root;
}
pre=root;
inorder(root.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null) return null;
inorder(pRootOfTree);
}
}
``````

## 从前序与中序遍历序列构造二叉树

``````    public int index=0;
public TreeNode createTreeByPandI(int[] preorder, int[] inorder,int inbegin,int inend){
if(inbegin>inend) return null;
TreeNode root=new TreeNode(preorder[index]);
//找到根节点在中序遍历的位置
int rootindex=findIndex(inorder,inbegin,inend,preorder[index]);
if(rootindex==-1){
return null;
}
index++;
//创建左子树和右子树
root.left=createTreeByPandI(preorder,inorder,inbegin,rootindex-1);
root.right=createTreeByPandI(preorder,inorder,rootindex+1,inend);
return root;
}
public int findIndex(int[] inorder,int inbegin,int inend,int key){
for(int i=inbegin;i<=inend;i++){
if(key==inorder[i]){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(inorder==null ||preorder==null) return null;

return createTreeByPandI(preorder,inorder,0,inorder.length-1);
}
``````

## 从中序与后序遍历序列构造二叉树

``````public int index = 0;
public TreeNode createTreeByPandI(int[] postorder, int[] inorder,int inbegin,int inend){
if(inbegin>inend) return null;
TreeNode root=new TreeNode(postorder[index]);
//找到根节点在中序遍历的位置
int rootindex=findIndex(inorder,inbegin,inend,postorder[index]);
if(rootindex==-1){
return null;
}
index--;
//创建左子树和右子树
root.right=createTreeByPandI(postorder,inorder,rootindex+1,inend);
root.left=createTreeByPandI(postorder,inorder,inbegin,rootindex-1);
return root;
}
public int findIndex(int[] inorder,int inbegin,int inend,int key){
for(int i=inbegin;i<=inend;i++){
if(key==inorder[i]){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder==null ||postorder==null) return null;
index=postorder.length-1;
return createTreeByPandI(postorder,inorder,0,inorder.length-1);
}
``````

## 根据二叉树创建字符串

``````  public void treeToString(TreeNode root,StringBuilder sb){
if(root==null) return;
sb.append(root.val);
if(root.left!=null){
sb.append("(");
treeToString(root.left,sb);
sb.append(")");
}else{
if(root.right!=null){
sb.append("()");
}else{
return;
}
}
if(root.right==null){
return;
}else{
sb.append("(");
treeToString(root.right,sb);
sb.append(")");
}

}
public String tree2str(TreeNode root) {
if(root==null) return null;
StringBuilder sb=new StringBuilder();
treeToString(root,sb);
return sb.toString();
}
``````

## 二叉树的前序遍历、中序遍历、后续遍历（非递归版实现）

``````//前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<>();
List<Integer> ret=new ArrayList<>();
TreeNode cur=root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode top=stack.pop();
cur=top.right;
}
return ret;
}

//中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<>();
List<Integer> ret=new ArrayList<>();
TreeNode cur=root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode top=stack.pop();
cur=top.right;
}
return ret;
}

//后续遍历
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<>();
List<Integer> ret=new ArrayList<>();
TreeNode cur=root;
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){
stack.pop();
prev=top;//记录最近依次打印的结点
}else{
cur=top.right;
}
}
return ret;
}
``````

## 二叉树的完全性检验

``````public boolean isCompleteTree(TreeNode root) {
if(root==null) return true;
queue.offer(root);
boolean flg=false;
while(!queue.isEmpty()){
TreeNode tmp=queue.poll();
if(flg){
if(tmp.left!=null || tmp.right!=null){
return false;
}
}
if(tmp.left!=null && tmp.right!=null){//左右孩子都有
queue.offer(tmp.left);
queue.offer(tmp.right);
}else if(tmp.right!=null){//只有右孩子
return false;
}else if(tmp.left!=null){//只有左孩子
queue.offer(tmp.left);
flg=true;
}else{//左右孩子都没
flg=true;;
}
}
return true;
}
``````