二叉数＜二＞

二叉树

一、二叉树相关函数的实现
- 1.求二叉树的结点个数
- 2.求二叉树叶子结点的个数
- 3.求二叉树第k层结点的个数
- 4.求二叉树的高度
- 5.求二叉树中值为val的所在结点
- 6.判断该二叉树是不是满二叉树
二、二叉树的基础面试题
- 2.1 检查两颗树是否相同。
- 2.2判断是不是另一颗的子树
- 2.3二叉树的最大深度
- 2.4判断二叉树是否是平衡二叉树
- 2.5判断是否是对称二叉树
三、二叉树的进阶面试题
- 3.1 二叉树的构建及遍历。
- 3.2 二叉树的分层遍历。
- 3.3 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
- 3.4 二叉树搜索树转换成排序双向链表。
- 3.5 根据一棵树的前序遍历与中序遍历构造二叉树。
- 3.6 根据一棵树的中序遍历与后序遍历构造二叉树。
- 3.7 二叉树创建字符串。

一、二叉树相关函数的实现 1.求二叉树的结点个数

遍历思路求二叉树结点个数

// 遍历思路-求结点个数
    static int size = 0;
    public void getSize1(TreeNode root){
        if (root==null) return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

子问题思路求二叉树结点个数

    public int getSize2(TreeNode root){
        if (root==null) return  0;
        return getSize2(root.left)+getSize2(root.right)+1;
    }

2.求二叉树叶子结点的个数

遍历思路求二叉树结点个数

    static int leafSize = 0;
   public  void getLeafSize1(TreeNode root){
        if (root==null) return;
        if(root.left==null && root.right==null){
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
   }

子问题思路求二叉树结点个数

    public int getLeafSize2(TreeNode root){
       if (root==null) return 0;
       if(root.left==null && root.right==null) return 1;
       return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

3.求二叉树第k层结点的个数

    public int getKLevelSize(TreeNode root,int k){
       if(root==null ) return 0;
       if(k ==1) return 1;
       return getKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1);
    }

4.求二叉树的高度

    public int getHeight(TreeNode root){
        if(root==null) return 0;
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?leftHeight+1 :rightHeight+1;
    }

5.求二叉树中值为val的所在结点


    public TreeNode find(TreeNode root,char val){
        if(root==null) return null;
        if(root.val==val) return root;

        TreeNode left=find(root.left,val);
        if(left!=null) return  left;

        TreeNode right=find(root.right,val);
        if(right!=null) return  right;
        return null;
    }

6.判断该二叉树是不是满二叉树

// 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){

        if(root == null) return true;
        Queue 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 top=queue.peek();
            if(top!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }

二、二叉树的基础面试题 2.1 检查两颗树是否相同。

LeetCode OJ 相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
            //先考虑p q 可能出现的情况  
        //p为空 q不为空 q 为空p不为空  返回false
        if(p!=null&&q==null || p==null&& q!=null){
            return false;
        }
        //p q都为空则返回 true
        if(p==null && q==null){
            return true;
        }

        //如果两个都不为空则判断根节点是否相同  若不相同则 返回false
        if(p.val!=q.val)
            return false;

        //递归 判断p q的左右子树是否相同 若同时为true 则这这两颗二叉树也相同    
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

2.2判断是不是另一颗的子树

OJ另一颗树的子树

class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {
            //先考虑p q 可能出现的情况  
        //p为空 q不为空 q 为空p不为空  返回false
        if(p!=null&&q==null || p==null&& q!=null){
            return false;
        }
        //p q都为空则返回 true
        if(p==null && q==null){
            return true;
        }

        //如果两个都不为空则判断根节点是否相同  若不相同则 返回false
        if(p.val!=q.val)
            return false;

        //递归 判断p q的左右子树是否相同 若同时为true 则这这两颗二叉树也相同    
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //root一个为空 则返回 false
        if(root==null ) return false;
        //先判断这两颗树是否相等     若相等则返回true
        if(isSameTree(root,subRoot)) return true;
        //两个树不相等
        //这时再判断subRoot是不是root 左子树的子树 如果是则返回true
        if(isSubtree(root.left,subRoot)) return true;
        //这时再判断subRoot是不是root 右子树的子树 如果是则返回true
        if(isSubtree(root.right,subRoot)) return true;
        //最后都没有返回true 则返回false
        return false;
    }
}

2.3二叉树的最大深度

二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        //结点为null返回0
        if(root==null) return 0;
        int left=maxDepth(root.left);//左子树的最大深度
        int right=maxDepth(root.right);//右子树的最大深度

        //返回左右子树最大深度+1    
        return left>right ? left+1 : right+1;

    }
}

2.4判断二叉树是否是平衡二叉树

平衡二叉树
平横二叉树：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        int left=maxDepth(root.left); //左子树的最大深度
        int right=maxDepth(root.right); //右子树的最大深度


        //如果左右子树都是平衡二插树 则返回此结点为根节点的树的高度
        if(left >=0 && right>=0 &&Math.abs(left-right)<=1){
            return left>right ? left+1 : right+1;
        }else{//若该结点作为根节点的树不是平衡二叉树则放回-1 该结点为空也返回-1
            return -1;
        }
        

    }
    public boolean isBalanced(TreeNode root) {
        //如果为空返回 true
        if(root==null) return true;
        return maxDepth(root)>=0;
    }
}

2.5判断是否是对称二叉树

对称二叉树

class Solution {
    public boolean isSymmetricChild(TreeNode p,TreeNode q){
        // p q 都为空 返回true
        if(p==null && q==null) return true;
        //p为空 q不为空  返回false
        if(p==null && q!=null) return false;
        //p不为空 q为空 返回fasle
        if(p!=null && q==null) return false;
        // 根节点不同则返回 false
        if(p.val!=q.val) return false;

        //递归判断p。left与q。right  和 p。right与q.left是否对称
        return (isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left));
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null ) return true;
        //左右子树都是对称的 则该根节点的树为对称二叉树
        return (isSymmetricChild(root.left,root.right));
            
    }
}

三、二叉树的进阶面试题 3.1 二叉树的构建及遍历。

二叉树的构建和遍历
构建结点
1.创建静态变量 i 记录字符串遍历的位置，在函数里创建root结点
2.如果当前字符为#则什么也不做 i++
3.若当前字符不为# 则让root 结点的值等于当前字符 i++
4.接下来在递归构建 root 的左右子树
5.最后返回root

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 TreeCreat(String str){
            TreeNode root=null;
            if(str.charAt(i)!='#'){
                root=new TreeNode(str.charAt(i));
                i++;
                root.left=TreeCreat(str);
                root.right=TreeCreat(str);
            }else{
                i++;
            }
        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 sc=new Scanner(System.in);
        while (sc.hasNextLine()){
            String str=sc.nextLine();
            TreeNode root=TreeCreat(str);
            inOrderTraversal(root);
        }
    }
}

3.2 二叉树的分层遍历。

二叉树的分层遍历

class Solution {
    public List> levelOrder(TreeNode root) {
        
        List> res=new ArrayList<>();
        //放最后遍历的结果
        if(root ==null) return res;
        
        Queue queue=new linkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size=queue.size();//用于记录当前层元素的个数
            List list=new ArrayList<>();
            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--;
            }
            res.add(list);
        }
           
        return res;
    }
}

3.3 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

二叉树的最近公共祖先
思路
1.判断当前root是否等于 p q 等于直接返回
2.递归遍历root的左右子树（如果找到就返回那个结点，找不到返回null）
3.最终情况分为四种：a.左右都不为空则直接返回root（p q在两边） b.左右一个为空一个不为空则返回不为空的（若p q 都在左边或者 p q都在右边）c。其他情况返回null；

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root ==q || root==p) return root;  //如果root==p ||q 则直接返回root
        TreeNode left=lowestCommonAncestor(root.left,p,  q); //先递归找左子树
        TreeNode right=lowestCommonAncestor(root.right, p,  q);//递归找右子树

        if(left!=null &&right!=null){ //左右子树都不为null 返回 root
            return root;
        }else if(left==null && right!=null){//左右子树谁不为空返回谁
            return right;
        }else if(left!=null && right==null){
            return left;
        }else{//left==null && right==null
            return null;
        }            
    }
}

3.4 二叉树搜索树转换成排序双向链表。

二叉树搜索树转换成排序双向链表

public class Solution {
   TreeNode prev=null;//记录先前结点
    public void ConvertChild(TreeNode pcur) {
        if(pcur==null) return;
        //采用中序遍历  合成链表 链表才有序
        ConvertChild(pcur.left);
        pcur.left=prev;   //让当前结点的left指向他的先前结点
        if(prev!=null){  //prev为空 则它不需要向后指 （第一次）
            prev.right=pcur;//让先前结点指向自己
        }
        prev=pcur;//先前结点向后移动
        ConvertChild(pcur.right);
    }
    //结点的left 记录先前结点 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.5 根据一棵树的前序遍历与中序遍历构造二叉树。

根据前序和中序构建二叉树

class Solution {
    public int pi=0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int begin ,int end) {
        if(begin>end) return null;  //说明遍历结束
        //构建树
        TreeNode root= new TreeNode(preorder[pi]);   
        int ri=findIndex(inorder,begin,end,preorder[pi])  ; //找先序中pi下标对应值在中序遍历中的值
        pi++;
        //递归构建左子树
        root.left=buildTreeChild(preorder,inorder,begin,ri-1);
        //递归构建右子树
        root.right=buildTreeChild(preorder,inorder,ri+1,end);
        return root;
    }
    //查找中序遍历中 begin end 之间 值为 key 的下标 
    public int findIndex(int[] inorder,int begin,int end,int key) {
        for(int i = 0;i <= end;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
}

3.6 根据一棵树的中序遍历与后序遍历构造二叉树。

根据中序和后序遍历二叉树

class Solution {
    public static int pi;
    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int begin,int end){
        if(begin>end) return null;
        TreeNode root=new TreeNode(postorder[pi]);
        int ri=find(inorder,begin,end,postorder[pi]);
        pi--;
        root.right=buildTreeChild(inorder,postorder,ri+1,end);
        root.left=buildTreeChild(inorder,postorder,begin,ri-1);

        return root;
    }
     public int find(int[] inorder,int begin,int end,int key) {
        for(int i = 0;i <= end;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pi=postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
}

3.7 二叉树创建字符串。

二叉树创建字符串
思路
1.先序遍历如果当前为空直接return
2.不为空放入StringBuilder 中
3.判断左子树情况{ [左不为空：先加 ‘(’ 、放数据、’)’ ]、[左为空右也为空：直接return]、[左为空右不为空：将 ‘（）’放入]}
4.判断右子树情况{[右为空：直接return]、[右不为空：先加 ‘(’ 、放数据、’)’ ]}

class Solution {
    public void tree2strChild(TreeNode t,StringBuilder sb){
        if(t==null) return;
        sb.append(t.val);//现将t的值放入 sb 中
        if(t.left==null){
            if(t.right==null){ //左为空 右也为空
                return;
            }else{//最为空 右不为空
                sb.append("()");
            }
        }else{//如果做不为空
            sb.append("(");
            tree2strChild(t.left,sb);
            sb.append(")");
        }
        if(t.right==null){  //右为空
            return ;
        }else{//右不为空
            sb.append("(");
            tree2strChild(t.right,sb);
            sb.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        tree2strChild(root,sb);
         return sb.toString();
    }
}

二叉数＜二＞

Java相关栏目本月热门文章