【二叉树】之力扣牛客必刷题

导读:本篇文章讲解 【二叉树】之力扣牛客必刷题,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

目录

1. 相同的树

2. 另一颗树的子树

3. 二叉树的最大深度 

4. 平衡二叉树

5. 对称二叉树

6. 二叉树的构建及遍历

7. 二叉树的层序遍历 

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

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

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

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

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

13. 二叉树的前序遍历

14. 二叉树的中序遍历

15. 二叉树的后序遍历


1. 相同的树

链接  100. 相同的树 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

【二叉树】之力扣牛客必刷题

 上代码

时间复杂度O(min(m,n))

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        if(p.val != q.val) {
            return false;
        }
        // p!=null && q!=null 并且 p.val == q.val
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
    }
}

 2. 另一颗树的子树

链接   572. 另一棵树的子树 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

时间复杂度O(m*n)

【二叉树】之力扣牛客必刷题

 上代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        if(p.val != q.val) {
            return false;
        }
        // p!=null && q!=null 并且 p.val == q.val
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == 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;
    }
}

3. 二叉树的最大深度 

链接   104. 二叉树的最大深度 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

上代码

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftTree  = maxDepth(root.left);
        int rightTree = maxDepth(root.right);
        return (leftTree > rightTree ? leftTree+1 : rightTree+1 ); 
    }
}

 4. 平衡二叉树

链接   110. 平衡二叉树 – 力扣(LeetCode)

题目要求

   【二叉树】之力扣牛客必刷题

 分析一下

【二叉树】之力扣牛客必刷题

 上代码

(1)时间复杂度O(n^2)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftTree  = maxDepth(root.left);
        int rightTree = maxDepth(root.right);
        return (leftTree > rightTree ? leftTree+1 : rightTree+1 ); 
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
       
        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
}

(2)前面一种方法,每次每个结点都要算一次高度,比如刚开始算根节点时,已经把根节点的左子树结点算过了,而且如果前面左子树的子树不平衡,后面还要继续判断,每次这样做,就造成了空间上的浪费

那么我们可以在求高度时,顺序就可以判断是否平衡

class Solution {
     public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftTree  = maxDepth(root.left);
        int rightTree = maxDepth(root.right);
        if (leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree - rightTree) <= 1) {
            return Math.max(leftTree,rightTree) + 1;
        }else {
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return maxDepth(root) >= 0;
    }
}

5. 对称二叉树

链接   101. 对称二叉树 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

【二叉树】之力扣牛客必刷题

 上代码

class Solution {
    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 || rightTree == null && leftTree != null) {return false;} 
        if(leftTree == null && rightTree == null) {
            return true;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) &&
        isSymmetricChild(leftTree.right,rightTree.left);
    }
}

6. 二叉树的构建及遍历

链接   二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

【二叉树】之力扣牛客必刷题

 上代码

import java.util.*;

public class Main {
class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(char val) {
        this.val = val;
    }
}
    public int i = 0;
    public TreeNode createTree(String s) {
        TreeNode root = null;
        if(s.charAt(i) != '#') {
            root = new TreeNode(s.charAt(i));
            i++;
            root.left = createTree(s); 
            root.right = createTree(s); 
        }else{
             i++;
        }
        return root;
    }
    public 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 scan = new Scanner(System.in);
        while(scan.hasNextLine()) {
            String s = scan.nextLine();
            Main m = new Main();
            TreeNode root = m.createTree(s);
            m.inorder(root);
        }
    }
}

7. 二叉树的层序遍历 

链接   102. 二叉树的层序遍历 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题 分析一下

这道题和前一篇写过的层序遍历唯一不同的地方就是

【二叉树】之力扣牛客必刷题

 上代码

class Solution {
    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> row = new ArrayList<>();
            while(size > 0) {
               TreeNode cur = queue.poll();
               size--;
               row.add(cur.val);
               if (cur.left != null) {
                   queue.offer(cur.left);
               }
               if (cur.right != null) {
                   queue.offer(cur.right);
               }  
            }
            ret.add(row);
        }
        return ret;
    }
}

 

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

 链接  236. 二叉树的最近公共祖先 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

(1)方法一,看根结点是不是,递归左右子树

【二叉树】之力扣牛客必刷题

 (2)方法二,使用两个栈来找公共祖先

【二叉树】之力扣牛客必刷题

 上代码

 (1)方法一的代码

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

(2)方法二的代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == null || q == 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) {
            int tmp = size1 - size2;
            while(tmp != 0) {
                stack1.pop();
                tmp--;
            }
        }else {
             int tmp = size2 - size1;
            while(tmp != 0) {
                stack2.pop();
                tmp--;
            }
        }
        //两个栈个数一样
        while(!stack1.empty() && !stack2.empty()) {
            if(stack1.peek() == stack2.peek()) {
                return stack1.peek();
            }else {
                stack1.pop();
                stack2.pop();
            }
        }
        return null;//没有公共祖先
    }
//找到根节点到指定节点路径上所有结点,放在栈中
    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 ret1 = getPath(root.left,node,stack);
        //只能说明左边没有node
        if(ret1) {
            return true;
        }
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2) {
            return true;
        }
        //根节点不是   根左不是  根右也不是
        stack.pop();
        return false;
    }
}

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

 链接   二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

【二叉树】之力扣牛客必刷题

 上代码

public class Solution {
    TreeNode prev = null;
    public void ConvertChild(TreeNode root) {
        if(root == null) return;

        ConvertChild(root.left);
        root.left = prev;
        if(prev != null) {
              prev.right = root;
        }
        prev = root;
        ConvertChild(root.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;
    }
}

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

 链接   105. 从前序与中序遍历序列构造二叉树 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

【二叉树】之力扣牛客必刷题

 上代码

class Solution {
    public int preIndex = 0;
    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend){
        //没有了左树或者没有了右树
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //找到当前根节点 在中序遍历中的位置
        int rootIndex = findInorder(inorder,preorder[preIndex],inbegin,inend);
        preIndex++;
        root.left = buildTreeChild(preorder, inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder, inorder,rootIndex+1,inend);
        return root;
    }

    private int findInorder(int[] inorder,int val,int inbegin,int inend){
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
}

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

 链接  106. 从中序与后序遍历序列构造二叉树 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 分析一下

【二叉树】之力扣牛客必刷题

 上代码

class Solution {
    public int postIndex = 0;
    private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
        //没有了左树或者没有了右树
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        //找到当前根节点 在中序遍历中的位置
        int rootIndex = findInorder(inorder,postorder[postIndex],inbegin,inend);
        postIndex--;
        root.right = buildTreeChild(postorder, inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postorder, inorder,inbegin,rootIndex-1);
        return root;
    }

    private int findInorder(int[] inorder,int val,int inbegin,int inend){
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
}

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

 链接     606. 根据二叉树创建字符串 – 力扣(LeetCode)

 题目要求【二叉树】之力扣牛客必刷题

分析一下

【二叉树】之力扣牛客必刷题

 上代码

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();
    }
    private void tree2strChild(TreeNode t, StringBuilder sb) {
        if(t == null) return ;
        sb.append(t.val);

        if(t.left != null) {
            sb.append("(");
            tree2strChild(t.left,sb);
            sb.append(")");
        }else {
            if(t.right == null) {
                return;
            }else {
                sb.append("()");
            }
        }
        if(t.right == null) {
            return;
        }else {
            sb.append("(");
            tree2strChild(t.right,sb);
            sb.append(")");
        }
    }
}

13. 二叉树的前序遍历

链接 144. 二叉树的前序遍历 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 上代码

(1)遍历递归思路:在方法的外面new ,遇到合适的元素结点就给进放

class Solution {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return ret;   
        ret.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ret;   
    }
}

(2)子问题思路:将左边遍历完放进去,再遍历右边完放进去,也就是大问题变小问题

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;   
        ret.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = preorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;   
    }

(3)方法三:用栈实现非递归前序遍历 

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || ! stack.empty()) {
        while(cur != null) {
            stack.push(cur);
            ret.add(cur.val);
            cur = cur.left;
        } 
        TreeNode top = stack.pop();
        cur = top.right;
        }
        return ret;
    }
}

14. 二叉树的中序遍历

链接 94. 二叉树的中序遍历 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 上代码

(1)遍历递归思路:在方法的外面new ,遇到合适的元素结点就给进放

class Solution {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
    if(root == null) return ret;   
    inorderTraversal(root.left);
    ret.add(root.val);
    inorderTraversal(root.right);
    return ret;  
    } 
}

 (2)子问题思路

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;   
        List<Integer> leftTree = inorderTraversal(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;   
    
    }
}

 (3)方法三:用栈实现非递归后序遍历 

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null ) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()) {
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        } 
        TreeNode top = stack.pop();
        ret.add(top.val);
        cur = top.right;
        }
        return ret;
    }
}

 


15. 二叉树的后序遍历

链接 145. 二叉树的后序遍历 – 力扣(LeetCode)

题目要求

【二叉树】之力扣牛客必刷题

 上代码

(1)子问题

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;   
        List<Integer> leftTree = postorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = postorderTraversal(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;   
    
    }
}

(2)遍历递归

class Solution {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {

    if(root == null) return ret;   
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    ret.add(root.val);
    return ret;   
    }
}

(3)方法三:用栈实现非递归后序遍历 

后序遍历和前序遍历不同的是

class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null ) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        TreeNode cur = root;
        while(cur != null || !stack.empty()) {
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        } 
        TreeNode top = stack.peek();
//top.right 如果已经被访问了,也要弹出top所指向的结点
        if(top.right == null || top.right == prev) {
            stack.pop();
            ret.add(top.val);
            prev = top;
        }else {
             cur = top.right;
        }
        }
        return ret;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/91248.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!