二叉树练习题

文章目录

• 1. 获取树中节点的个数
• 2. 获取叶子节点的个数 - (遍历思路、子问题思路)
• 3. 获取第K层节点的个数
• 4. 获取二叉树的高度
• 5. 检测值为value的元素是否存在
• 6. 判断一棵树是不是完全二叉树
• 7. 相同的树
• 8. 另一棵树的子树
• 9. 二叉树的最大深度 - 和上面二叉树高度相同
• 10. 平衡二叉树
• 11. 对称二叉树
• 12. 二叉树遍历
• 13. 层序遍历
• 14. 二叉树的最近公共祖先
• 15. 二叉搜索树与双向链表
• 16. 从前序与中序遍历序列构造二叉树
• 17. 从中序与后序遍历序列构造二叉树
• 18. 根据二叉树创建字符串
• 19. 前序遍历 - 非递归
• 20. 中序遍历 - 非递归
• 21. 后序遍历 - 非递归

1. 获取树中节点的个数

int count = 0;
int size(TreeNode root){
    if (root == null){
        return 0;
    }
    count++;
    return size(root.left)+size(root.right);
}

int size1(TreeNode root){
    if (root == null) return 0;
    //左子树和右子树之和+根节点
    return size1(root.left)+size1(root.right)+1;
}

2. 获取叶子节点的个数 - (遍历思路、子问题思路)

• 遍历思路：遍历到叶子结点，就让计数器++

int leafCount = 0;
void getLeafNodeCount(TreeNode root){
    if(root == null){
        return;
    }
    //左子树和右子树都为null时，是叶子结点
    if (root.left == null && root.right ==null){
        leafCount++;
    }
    //递归左子树和右子树
    getLeafNodeCount(root.left);
    getLeafNodeCount(root.right);

• 子问题思路 ：左树叶子数 +右树叶子数 = 整棵树的叶子

int leafCount1 = 0;
int getLeafNodeCount1(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null &&root.right == null){
        //当前的root没有子树，自己就是叶子节点
        return 1;
    }
    return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
}

3. 获取第K层节点的个数

• 子问题思路：是根节点的第k层，也就是第二层结点的第k-1层

public int getKLevelNodeCount(TreeNode root,int k){
    if (root == null || k <= 0){
        return 0;
    }
    if (k == 1){ //当k=1时，第一层
        return 1;
    }
    //k不为1时：递归
    return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
}

4. 获取二叉树的高度

• 子问题思路：左树的高度和右树的高度 取最大值 然后+1（根节点）= 整棵树的高度
• 下面的函数时间复杂度：O(n) （看递归的次数，每个结点都递归，次数为n）
• 空间复杂度：O(k) k=log2(n) （空间复杂度为数的高度）

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


}
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;

   //return getHeight(root.left) > getHeight(root.right)? (getHeight(root.left)+1):(getHeight(root.right)+1);
   //递归的次数太多了，重复计算了好多次，err
        //超出规定的运行时间：1.死循环 2.递归的次数太多了
}

5. 检测值为value的元素是否存在

TreeNode find(TreeNode root,char val) {
    if (root == null) return null;
    if (root.val == val){
        return root;
    }
    TreeNode ret = find(root.left,val);
    if(ret!=null){
        return ret;
    }
    ret = find(root.right,val); //如果左子树没有值为value的元素，看看右子树
    if (ret != null){
        return ret;
    }
    return null;
}

6. 判断一棵树是不是完全二叉树

• 思路：root为空返回true，不为空时，建立一个队列，将root放入队列，
• 队列不为空时，每次取出队列队头元素，对头元素不为null，则加入对头元素的左子树和右子树，为null则中止循环
• 之后，队列不为空时，检测队列中所有元素，如果都是null则为true，如果有别的元素，则为false

{
    if(root == null){
        return true;
    }
    //队列
    Queue queue = new LinkedList<>();
    queue.offer(root);//将根入队列
    //循环
    while (!queue.isEmpty()){// 队列不为空
        TreeNode cur = queue.poll(); //取出队头元素给cur
        if (cur != null){  //当取出的队头不为null时，加入其左子树和右子树两个元素
            queue.offer(cur.left);
            queue.offer(cur.right);
        }else {
            break; //为null时，中止循环
        }
    }
    //看队列剩下的元素是否都为null，如果有不为null的元素，那么就不是完全二叉树
    while(!queue.isEmpty()){
        TreeNode top = queue.peek();
        if(top != null){
            return false;
        }
        queue.poll();
    }
    return true;
}

7. 相同的树

时间复杂度：O(min(M,N))

• https://leetcode.cn/problems/same-tree/

public boolean isSameTree(TreeNode p, TreeNode q) {
    if(p == null && q == null){ //p和q都为空
        return true;
    }
    if(p == null && q!=null || p!=null && q == null){ //p为空或者q为空
        return false;
    }
    if(p.val != q.val){ //p和q的数值不同
        return false;
    }
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

8. 另一棵树的子树

• https://leetcode.cn/problems/subtree-of-another-tree/
• 思路：
• 1.先判断 两棵树 是不是两棵相同的树

•  2.如果不是，分别判断，subRoot是不是root的左子树或者右子树
  

• 时间复杂度：O(m * n)

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //一个为空，有个不为空
        if(root == null || subRoot == null){
            return false;
        }
//        if(root == null && subRoot == null) {
//            return true;
//        }
//        if(root != null && subRoot == null && root == null && subRoot != null) {
//            return false;
//        } 这两个条件和上面的条件相同
        //根节点和subroot是不是两颗相同的树
        if(isSameTree(root,subRoot)){
            return true;
        }
        //判断subRoot是不是root的左子树或者右子树
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;

    }

9. 二叉树的最大深度 - 和上面二叉树高度相同

• https://leetcode.cn/problems/maximum-depth-of-binary-tree/
• 时间复杂度：O(n);

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

}

10. 平衡二叉树

• https://leetcode.cn/problems/balanced-binary-tree/

//时间复杂度：O(n);
public int Height(TreeNode root){
    if(root == null){
        return 0;
    }
    int leftHeight = Height(root.left);
    int rightHeight = Height(root.right);
    return leftHeight > rightHeight? leftHeight+1 :rightHeight+1;
}
// 时间复杂度：O(N^2)
//一棵树 要是平衡二叉树，那么每棵子树都是平衡二叉树
public boolean isBalanced(TreeNode root) {
     if(root == null){
        return true;
     }
     int left = Height(root.left);
     int right = Height(root.right);
//左树高度和右树高度差小于1，同时满足root的左树是平衡的，右树也是平衡的
     return (Math.abs(left - right)<=1) && isBalanced(root.left) && isBalanced(root.right);
    }

//为了减少时间复杂度，一边检测高度，一边反馈是否平衡

public int Height2(TreeNode root){
     if(root == null){
        return 0;
     }
     int leftHeight = Height(root.left);
     int rightHeight = Height(root.right);
     //如果左右子树的差值大于1，则不平衡，返回
     //因为返回-1之后，另一各子树可能会为0，差值就变成了等于1，返回1，所以需要制止这种，在条件中加入左子树和右子树必须>=0
     if(leftHeight >=0 && rightHeight>=0 && Math.abs(leftHeight-rightHeight)<=1){
           return Math.max(leftHeight,rightHeight) + 1;
     }else{
          //说明不平衡
           return -1;
     }
}
public boolean isBalanced2(TreeNode root) {
     if(root == null){return true;}
        return Height(root)>=0;
     }

11. 对称二叉树

https://leetcode.cn/problems/symmetric-tree/

public 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);
}

public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
}

12. 二叉树遍历

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    public  TreeNode(char val){
        this.val = val;
    }
}
class solution{
    public static int i = 0; //i遍历字符串
    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++; //当为#时，表示为空树，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 的区别,
        // hasNext遇到空格结束，hasNextLine遇到空格不结束
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
        }
    }

13. 层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

public void levelOrder(TreeNode root) {
    //队列表示
    Queue queue= new LinkedList<>();
    if (root == null){
        return;
    }
    queue.offer(root);
    if(!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);
        }
    }
}

//新建一个队列，在队列中，最先加入根节点，之后移除，再加入根节点的左右节点(前提是，如果为null就不加入队列中）
//list - 每层节点数，都是看队列中的节点数量
public List> levelOrder1(TreeNode root) {
        List> ret = new ArrayList<>();
        if(root == null){
            return ret; //root == null时，希望得到的数值是空的，但是地址不为空
        }
        Queue queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size(); //这个值代表 当前层有多少个结点
            List list = new ArrayList<>(); //新建list装一层的结点
            while(size != 0){
                TreeNode cur = queue.poll();
               // list.add(cur.val);
                if(cur.left!=null){ //与遍历节点问题不同的是：如果是null就不添加到que中
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

14. 二叉树的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

//方法1：二叉搜索树的思想 （左子树数值<根数值<右子树数值）
 // 分三种情况，1.p和q有一个是root，那么公共祖先就是root；2.p和q在root的两侧，公共祖先是root；
 // 3.p和q都在root的左树或者右树，公共祖先在root的左树或者右树当中

 public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
     if(root == null) {
         return null;
     }

     if(root == p || root == q) {
         return root;
     }

     TreeNode leftT = lowestCommonAncestor(root.left,p,q);
     TreeNode rightT = lowestCommonAncestor(root.right,p,q);

     if(leftT != null && rightT != null) {
         return root;
     }else if(leftT != null) {
         return leftT;
     }else {
         return rightT;
     }
 }

 //方法2：思路：假设这可二叉树 是使用孩子双亲表示法 表示的
    //可以把问题转换为 链表求交点 但是二叉树 每个结点 是没有双亲结点的
    //1.用两个栈存储路径，
    //2.求栈的大小
    //3.让栈中多的元素 取出差值个 元素
    //4.之后再同时出栈，如果栈顶元素相同，则为公共祖先


    //难点：如何去找到从根节点到一个指定节点的路径？

    //用两个栈表示p和q的路径
    //找到p,q的地址
    //root：根节点 node:指定的节点 stack:存放从根节点到指定节点的路径
public Boolean getPath(TreeNode root,TreeNode node,Stack stack){
        if(root == null || node == null){
            return false;
        }
        //root不为null，将root入栈
        stack.push(root);

        if(root == node){
            return true;
        }
        //如果root!=node，先将root放入栈中
        //将左子树带入递归
        Boolean flg = getPath(root.left,node,stack);
        if(flg){
            return true; //如果在左子树中找到了，返回true
        }
        //左子树中没找到,在右子树中找
        flg = getPath(root.right,node,stack);
        if(flg){
            return true;
        }
        //如果不是true，则从栈中去除
        stack.pop();
        return false;
    }
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        //建立两个栈，一个p，一个q
        Stack stack1 = new Stack<>();
        Stack stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        //看p和q的栈中元素多少，多的栈就将元素去除size个
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2){
            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;
    }

15. 二叉搜索树与双向链表

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

// 排序：可以中序遍历这棵二叉搜索树 left变成双向链表的前驱，right变成双向链表的后继
// 需要在遍历过程中修改每个结点的left和right
//修改指向是重点
//相当于对二叉搜索树进行排序

TreeNode prev = null;
public void inorder1(TreeNode pCur) {
        if (pCur == null) {
            return;
        }
        //左子树
        inorder(pCur.left);
        pCur.left = prev; //将pCur的左修改为prev
        if (prev != null) {
            prev.right = pCur;//prev的右就为pCur
        }
        prev = pCur; //prev修改到pCur
        //右子树
        inorder(pCur.right);

    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        inorder(pRootOfTree);
        // 创建头结点
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }
        return head;

    }

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

• https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

  public int preIndex = 0;
  //用先序遍历和中序遍历创建二叉树
  public TreeNode createTreeByPandI(int[] preorder,int[] inorder,int inbegin,int inend){
        //递归中止条件
        if(inbegin > inend){
            //如果满足这个条件说明没有左树也没有右树，是终节点
            return null;
        }
        //建立根节点
        TreeNode root = new TreeNode(preorder[preIndex]);
        //寻找根节点在中序遍历数组中的位置
        int rootIndex = findIndexOdI(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        //分别建立左子树 和 右子树,顺序不能颠倒
        root.left = createTreeByPandI(preorder,inorder,inbegin,rootIndex-1);
        root.right = createTreeByPandI(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    //在中序遍历中寻找前序遍历下标为pi的数在哪里
    private int findIndexOdI(int[] inorder,int inbegin,int inend,int key){
        for(int i = inbegin;i<=inend ; i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    //将先序遍历pi下标的元素创建为root
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null){
            return null;
        }
        return createTreeByPandI(preorder,inorder,0,inorder.length-1);
    }

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

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

public int postIndex = 0;
 public TreeNode createByPandI(int[] inorder,int[] postorder,int inbegin,int inend){
        //中止条件
        if(inbegin>inend){
            return null;
        }

        TreeNode root = new TreeNode(postorder[postIndex]);
        //根节点在中序遍历的位置
        int rootIndex = findIndexOd(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;

        //因为后序遍历中根结点在最后，它的前一位在中序遍历的根节点的右子树
        //所以建立右子树，在加你左子树
        root.right = createByPandI(inorder,postorder,rootIndex+1,inend);
        root.left = createByPandI(inorder,postorder,inbegin,rootIndex-1);

        return root;

    }
    public int findIndexOd(int[] inorder,int inbegin,int inend,int key){
        for(int i = inbegin; i<= inend ; i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //如果为空，返回null
        if(inorder == null || postorder == null){
            return null;
        }
        postIndex = postorder.length-1;
        return createByPandI(inorder,postorder,0,inorder.length-1);
    }

18. 根据二叉树创建字符串

https://leetcode.cn/problems/construct-string-from-binary-tree/

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){
            return;
        }else{
            //左为空，右不为空时
            sb.append("(");
            sb.append(")");
        }
    }
    if(root.right != null){
        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();
}

19. 前序遍历 - 非递归

public void preOrder1(TreeNode root) {
        Stack stack = new Stack<>();
        TreeNode cur = root;
        while(cur!= null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop(); //记录根节点
            cur = top.right;

        }

    }

20. 中序遍历 - 非递归

public void inOrder1(TreeNode root) {
    //新建一个栈
    Stack stack = new Stack<>();
    TreeNode cur = root;
    while(cur!=null || !stack.empty()){
        while(cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.pop();
        System.out.println(top.val+" ");
        cur = top.right;
    }
}

21. 后序遍历 - 非递归

//左子树和右子树都为空的时候才能打印根节点
    public void postOrder1(TreeNode root) {
        Stack stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur!=null || !stack.empty()){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            //为了防止死循环 在条件中加一个打印过的不能再打印
            // 如果当前节点的右子树被打印过 或者 遍历过  直接弹出了
            if(top.right == null || prev == top.right){
                stack.pop();
                System.out.println(top.val+" ");
                prev = top;///记录一下 最近一次打印的结点

            }else{
                cur = top.right;
            }
        }
    }