目录
一、有关树的属性概念
1、结点的度:结点的子树个数称为结点的度,eg:A的度为6,有6个子树。
2、树的度:最大结点度为树的度,以上树的度为6;
3、树的高度或深度:树中结点最大层次;
4、父亲结点:若一个结点有子结点,则该结点就是子结点的父亲结点,eg:A是B的父亲结点。
二、树的应用
文件资源管理。
三、二叉树
1、特点:二叉树不存在度大于2的结点。
2、两种特殊的二叉树
(1)满二叉树:一棵二叉树,若每层的结点数都达到最大值,则该二叉树为满二叉树。即当满二叉树有k层时,结点个数为:2^k-1,第k层的结点数:2^(k-1);
(2)完全二叉树:相对于满二叉树来说,最后一层不全,但是从左到右连续有结点。满二叉树是特殊的完全二叉树。
3、二叉树的性质
(1)根结点为第一层,则第k层的最多结点数为:2^(k-1);k层二叉树最多结点数为2^k-1;
(2)n个结点的二叉树有n-1条边。
(3)根结点的个数为n0,度为2的结点个数为n2,则n0=n2+1;
证明:度为2的结点延伸出2条边,度为1的结点延伸出1条边,则:2*n2+n1+1=n=n0+n1+n2,即:n2+1=n0。
(4)根结点序号为i,则左孩子结点序号为2*i+1;右孩子结点序号为2*i+2.
(5)完全二叉树中,度为1的结点个数为0或1。
n0+n1+n2=n ----> n0+n1+n0-1=n ---> 2n0+n1-1=n ,若n为偶数,则n1=1;若n为奇数,则n1=0。
四、二叉树的遍历
1、先序遍历:根结点---左结点---右结点;
2、中序遍历:左结点---根结点---右结点;
3、后序遍历:左结点---右结点---根结点;
4、层序遍历:自上而下,自左至右逐层访问树的结点
eg:
先序遍历:1--2--3--4--5--6;
中序遍历:3--2--1--5--4--6;
后序遍历:3--2--5--6--4--1;
层序遍历:1--2--4--3--5--6;
已知先序遍历和中序遍历,可以求出后序遍历;
已知中序遍历和后序遍历,可以求出先序遍历;
无法根据先序和后序遍历,求出中序遍历。
五、二叉树相关oj题
1、非递归先序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<>();
List<Integer> list=new ArrayList<>();
if(root==null) return list;
TreeNode cur=root;
while(cur!=null||!(stack.empty())){
while(cur!=null){
stack.push(cur);
list.add(cur.val);
cur=cur.left;
}
TreeNode temp=stack.pop();
cur=temp.right;
}
return list;
}
}
2、非递归中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
if(root==null){
return list;
}
TreeNode cur=root;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode temp=stack.pop();
list.add(temp.val);
cur=temp.right;
}
return list;
}
3、非递归后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
if(root==null) return list;
TreeNode cur=root;
TreeNode flag=null;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode temp=stack.peek();
if(temp.right==null||temp.right==flag){
list.add(stack.pop().val);
flag=temp;
}else{
cur=temp.right;
}
}
return list;
4、递归先序遍历
public void preorderTraversal(TreeNode root) {
if(root==null) return;
System.out.print(root.val+" ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
5、递归中序遍历
public void inorderTraversal(TreeNode root) {
if(root==null) return;
inorderTraversal(root.left);
System.out.print(root.val+" ");
inorderTraversal(root.right);
}
6、递归后序遍历
public void postorderTraversal(TreeNode root) {
if(root==null) return;
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.val+" ");
}
7、层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list=new ArrayList<>();
if(root==null) return list;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> temp=new ArrayList<>();
while(size!=0){
TreeNode cur=queue.poll();
size--;
temp.add(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
list.add(temp);
}
return list;
}
8、获取树中结点个数
(1)先序遍历计算
public int count=0;
public int size(TreeNode root){
if(root==null) return 0;
count++;
size(root.left);
size(root.left);
return count;
}
(2)先序遍历子问题计算
public int size1(TreeNode root){
if (root==null) return 0;
return 1+size1(root.left)+size1(root.right);
}
9、获取树中叶子结点个数
(1)
public int getLeafNodeCount1(TreeNode root){
if (root==null) return 0;
if(root.left==null&&root.right==null){
count++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
return count;
}
(2)
public int getLeafNodeCount(TreeNode root){
if(root==null) return 0;
if(root.left==null&&root.right==null) return 1;
return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
}
10、获取第k层结点个数
public int getKLevelNodeCount(TreeNode root,int k){
if(root==null) return 0;
if(k==1) return 1;
return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
}
11、获取二叉树的高度
public int getHeight(TreeNode root){
if(root==null) return 0;
int a=getHeight(root.left);
int b=getHeight(root.right);
return 1+Math.max(a,b);
}
12、检测值为value的元素是否存在
public boolean find(TreeNode root,int val){
if(root==null)
return false;
if(root.val==val)
return true;
boolean flag1=find(root.left,val);
if(flag1)
return flag1;
boolean flag2=find(root.right,val);
if(flag2)
return flag2;
return false;
}
13、判断一棵树是不是完全二叉树
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 temp=queue.poll();
if(temp!=null){
return false;
}
}
return true;
}
14、判断两颗树是否相同
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null) return true;
if(p==null||q==null) return false;
if(p.val!=q.val) return false;
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
15、判断树是否是另一棵树的子树
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root==null||subRoot==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;
}
public boolean isSametree(TreeNode a,TreeNode b){
if(a==null&&b==null) return true;
if(a==null||b==null) return false;
if(a.val!=b.val) return false;
return isSametree(a.left,b.left)&&isSametree(a.right,b.right);
}
16、翻转二叉树
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
if(root.left==null&&root.right==null) return root;
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
17、判断树是不是对称二叉树
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
if(root.left==null&&root.right==null) return true;
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
if(leftTree==null&&rightTree==null) return true;
if(leftTree==null||rightTree==null) return false;
if(leftTree.val!=rightTree.val) return false;
return isSymmetricChild(leftTree.left,rightTree.right)&&
isSymmetricChild(leftTree.right,rightTree.left);
}
18、判断树是不是平衡二叉树
(1)重复计算
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
int a=maxHight(root.left);
int b=maxHight(root.right);
return Math.abs(a-b)<=1&&isBalanced(root.left)&&isBalanced(root.right);
}
public int maxHight(TreeNode root){
if(root==null) return 0;
int a=maxHight(root.left);
int b=maxHight(root.right);
return Math.max(a,b)+1;
}
(2)树下面不平衡时就结束计算
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
return maxHight(root)>=0;
}
public int maxHight(TreeNode root){
if(root==null) return 0;
int a=maxHight(root.left);
if(a<0) return -1; //左边某一处不平衡时,左边就一直返回-1,直到返回给根结点
int b=maxHight(root.right);
if(b<0) return -1;
if((Math.abs(a-b))<=1){
return Math.max(a,b)+1;
}else{
return -1;
}
}
19、找到两个指定节点的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> s1=new Stack<>();
Stack<TreeNode> s2=new Stack<>();
getPath(root,p,s1);
getPath(root,q,s2);
int size1=s1.size();
int size2=s2.size();
if(size1>size2){
int a=size1-size2;
while(a--!=0){
s1.pop();
}
}else if(size1<size2){
int a=size2-size1;
while(a--!=0){
s2.pop();
}
}
while(!s1.isEmpty()){
TreeNode t1=s1.pop();
TreeNode t2=s2.pop();
if(t1.val==t2.val){
return t1;
}
}
return null;
}
public boolean getPath(TreeNode root,TreeNode t,Stack<TreeNode> stack){
if(root==null){
return false;
}
stack.push(root);
if(root.val==t.val){
return true;
}
boolean left=getPath(root.left,t,stack);
if(left){
return true;
}
boolean right=getPath(root.right,t,stack);
if(right){
return true;
}
stack.pop();
return false;
}
}
20、二叉树的构建
import java.util.Scanner;
class TreeNode {
public char val;
public TreeNode right;
public TreeNode left;
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);
// 注意 hasNext 和 hasNextLine 的区别
String s = in.nextLine();
TreeNode root=create(s);
printf(root);
}
public static TreeNode create(String s){
TreeNode root=null;
char c=s.charAt(i);
if(c!='#'){
root=new TreeNode(s.charAt(i));
i++;
root.left=create(s);
root.right=create(s); //刚开始没有建立连接 返回时才建立连接
}else{
i++;
}
return root;
}
public static void printf(TreeNode root){
if(root==null){
return;
}
printf(root.left);
System.out.print(root.val+" ");
printf(root.right);
}
}
21、根据前序、中序,构建二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildChild(preorder,inorder,0,inorder.length-1);
}
public int a;
//不断缩小区间 先求左子树 再求右子树
public TreeNode buildChild(int[] preorder,int[] inorder,int start,int end){
if(start>end){
return null;
}
TreeNode root=new TreeNode(preorder[a]);
//找到该根结点的左右子树
int index=getIndex(inorder,root);
if(index==-1){
return null;
}
a++;
root.left=buildChild(preorder,inorder,start,index-1);
root.right=buildChild(preorder,inorder,index+1,end);
return root;
}
public static int getIndex(int[] inorder,TreeNode cur){
for(int i=0;i<inorder.length;i++){
if(inorder[i]==cur.val){
return i;
}
}
return -1;
}
}
22、根据中序、后序,构建二叉树
class Solution {
public int a;
public TreeNode buildTree(int[] inorder, int[] postorder) {
a=postorder.length-1;
return buildChild(inorder,postorder,0,inorder.length-1);
}
public TreeNode buildChild(int[] inorder,int[] postorder,int start,int end){
if(start>end){
return null;
}
TreeNode root=new TreeNode(postorder[a]);
//找到根结点的左右子树区间 先右子树 再左子树---因为后序是左右中
int index=getIndex(inorder,root);
if(index==-1){
return null;
}
a--;
root.right=buildChild(inorder,postorder,index+1,end);
root.left=buildChild(inorder,postorder,start,index-1);
return root;
}
public int getIndex(int[] inorder,TreeNode cur){
for(int i=0;i<inorder.length;i++){
if(inorder[i]==cur.val){
return i;
}
}
return -1;
}
}
23、二叉树创建字符串
class Solution {
public String tree2str(TreeNode root) {
StringBuffer s=new StringBuffer();
get(root,s);
return s.toString();
}
public void get(TreeNode root,StringBuffer s){
if(root==null){
return;
}
//先找左边
s.append(root.val);
if(root.left!=null){
s.append("(");
get(root.left,s);
s.append(")");
}else{
if(root.right==null){
return; //左边为空 右边为空不管
}else{
s.append("()");
}
}
//找右边
if(root.right!=null){
s.append("(");
get(root.right,s);
s.append(")");
}else{
return;
}
}
}