【数据结构】_8.二叉树OJ-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】_8.二叉树OJ。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目1：检查两棵树是否相同

2. 题目2：判断一棵树是否为另一棵树的子树

3. 题目3：翻转二叉树

4. 题目4：判断一棵树是否为平衡二叉树

5. 题目5：判断一棵树是否为对称二叉树

6. 题目6：二叉树的层序遍历

7. 题目7：二叉树的遍历

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

9. 题目9：根据前序与中序遍历构造二叉树

10. 题目10：根据中序与后序遍历构造二叉树

11. 题目11：根据二叉树创建字符串

12. 题目12：非递归实现二叉树前序遍历

13. 题目13：非递归实现二叉树中序遍历

14. 题目14：非递归实现二叉树后序遍历

1. 题目1：检查两棵树是否相同

题目链接：100. 相同的树 - 力扣（LeetCode）

解题思路：递归思路：判断根节点是否相同，左子树是否相同，右子树是否相同；

相同判定有两方面：结构与数值；

代码：文章来源地址https://www.toymoban.com/news/detail-652281.html

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 两树均为空
        if(p == null && q == null){
            return true;
        }
        // 两树一空一非空
        if((p == null && q != null)||(p != null && q == null)){
            return false;
        }
        // 两树均不为空
        // 两树根节点数据域值不同
        if(p.val != q.val){
            return false;
        }
        // 两树根节点数据域值相同
        return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
    }
}

时间复杂度：O(min(m,n))；其中mn分别为两棵树的结点数；

2. 题目2：判断一棵树是否为另一棵树的子树

题目链接：572. 另一棵树的子树 - 力扣（LeetCode）

解题思路：判断两棵树是否相同，递归判断一棵是否为另一棵的左子树，是否为其右子树；

代码：

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

时间复杂度：O(s * t)；

3. 题目3：翻转二叉树

题目链接：226. 翻转二叉树 - 力扣（LeetCode）

解题思路：在二叉树不为空时，将二叉树的左右子树交换，再递归交换左子树的左右子树和右子树的左右子树；

代码：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

4. 题目4：判断一棵树是否为平衡二叉树

题目链接：110. 平衡二叉树 - 力扣（LeetCode）

解题思路：

代码1：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);
        return  Math.abs(leftH - rightH) <2
        && isBalanced(root.left) 
        && isBalanced(root.right);
    }
    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);
    }
}

时间复杂度：O(N²)；

代码2：

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

时间复杂度：O（N）；

5. 题目5：判断一棵树是否为对称二叉树

题目链接：101. 对称二叉树 - 力扣（LeetCode）

代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == 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)||
        (leftTree != null && rightTree == null)){
            return false;
        }
        // 左右子树均不为空
        // 左右子树根节点数据不同
        if(leftTree.val != rightTree.val){
            return false;
        }
        // 左右子树根节点数据相同
        return isSymmetricChild(leftTree.left,rightTree.right) && 
        isSymmetricChild(leftTree.right, rightTree.left);

    }
}

6. 题目6：二叉树的层序遍历

题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

代码：

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

7. 题目7：二叉树的遍历

题目链接：二叉树遍历_牛客题霸_牛客网

代码：

import java.util.Scanner;
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            i=0;  // 将i置为0，防止多组测试i累加
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inOrder(root);
        }
    }
    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);
    }
}

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

题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

解题思路：

方法1：除过空树与pq二者之一为根结点的情况外，分为三种情况：第一种：pq分别在根的左右两边；第二种：pq都在根的左边或右边；第三种：pq中有一个结点是公共祖先；

代码：

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return null;
        }
        if(p == root || q == root){
            return root;
        }
        // 分别在根结点的左右子树查找目标结点
        TreeNode leftRet = lowestCommonAncestor(root.left, p, q);
        TreeNode rightRet = lowestCommonAncestor(root.right, p, q);
        // 第一种情况：左右子树均有目标结点则根结点为公共祖先
        if(leftRet != null && rightRet != null){
            return root;
        }else if(leftRet != null){
            // 第二种情况： 右子树没有查询到目标结点：两个目标结点均在左子树
            return leftRet;
            // leftRet已经记录了左子树查询到的第一个目标结点
            // 同时由于2个目标结点均在左子树，即已经记录到的leftRet即是两个结点的最近公共祖先
        }else if(rightRet != null){
            // 左子树没有查询到目标结点：两个目标结点均在右子树
            return rightRet;
            // 同第一个else-if语句，rightRet即是2个目标结点的最近公共祖先
        }
        return null;
    }

方法2：建两个栈，分别存储pq两结点从根结点开始途径的每一个结点，从结点多的栈开始出栈，从两个栈元素数量相同开始，两个栈同时弹出栈顶元素进行比较是否相同，相同则是公共祖先，不相同则依次比较下一个元素；

代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 建2个栈分别用于存放根结点root到目标结点p与q的路径结点
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root, p, stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root, q, stack2);
        // 判断栈大小，先出栈元素多的栈直至与另一个栈元素个数相同，两栈开始同时出栈元素
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1> size2){
            int size = size1 - size2;
            while(size != 0){
                stack1.pop();
                size--;
            }
        }else{
            int size = size2 - size1;
            while(size != 0){
                stack2.pop();
                size--;
            }
        }
        // 此时两栈元素个数已经相同
        // 当两个栈均不为空时，逐个元素对比
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            // 两栈栈顶元素不同则同时出栈
            if(stack1.peek() != stack2.peek()){
                stack1.pop();
                stack2.pop();
            }else{
                // 两栈栈顶元素相同：该结点为公共祖先
                return stack1.peek();
            }
        }
        return null;
    }
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack){
        // 查找从根结点root到目标结点node路径上的结点并存放到栈stack中
        if(root == null || node == null){
            return false;
        }
        // 将当前结点入栈
        stack.push(root);
        // 判断该结点是否为目标结点
        if(root == node){
            return true;
        }
        // 判断该结点左子树中是否有目标结点
        boolean ret1 = getPath(root.left, node, stack);
        if(ret1 == true){
            return true;
        }
        // 判断该结点右子树中是否有目标结点
        boolean ret2 = getPath(root.right, node, stack);
        if(ret2 == true){
            return true;
        }
        // 左右子树均查询无果，则出栈该结点并返回空
        stack.pop();
        return false;
    }
}

注：如果二叉树每个结点中存储了其父亲结点的地址，则改题等效于求两个链表的交叉结点问题；

9. 题目9：根据前序与中序遍历构造二叉树

题目链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

代码：

class Solution {
    public int i=0;  //用于前序preorder遍历
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder, 0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBgein, int inEnd){
        if(inBgein > inEnd){   // 没有子树
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);  // root结点
        // 在中序遍历inorder中定位根结点root位置
        int rootIndex = findIndex(inorder, inBgein, inEnd, preorder[i]);
        i++;
        // 在中序遍历中确定根结点位置后，其左为左树，右为右树
        root.left = buildTreeChild(preorder, inorder, inBgein, rootIndex-1);
        root.right = buildTreeChild(preorder, inorder, rootIndex+1, inEnd);
        return root;
    }
    private int findIndex(int[] inorder, int inBgein, int inEnd, int key){
        for(int i=inBgein; i<= inEnd;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}

10. 题目10：根据中序与后序遍历构造二叉树

题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

代码：

class Solution {
    public int i =0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        i = inorder.length-1;
        return  buildTreeChild(postorder, inorder, 0, inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inBegin, int inEnd){
        if(inBegin > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(postorder[i]);
        int rootIndex = findIndex(inorder, inBegin, inEnd, postorder[i]);
        i--;
        root.right = buildTreeChild(postorder, inorder, rootIndex+1, inEnd);
        root.left = buildTreeChild(postorder, inorder, inBegin, rootIndex-1);
        return root;
    }
    private int findIndex(int[] inorder, int inBegin, int inEnd, int key){
        for(int j=inBegin;j<=inEnd;j++){
            if(inorder[j] == key){
                return j;
            }
        }
        return -1;
    }
}

11. 题目11：根据二叉树创建字符串

题目链接：606. 根据二叉树创建字符串 - 力扣（LeetCode）

解题思路：分为以下三种情况：（1）结点左右均为空：直接返回；（2）结点左不为空右为空：无需为空结点增加括号；（3）结点左空右不为空，给空结点增加括号；

代码：

class Solution {
    public String tree2str(TreeNode root) {
        if(root == null){
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root, stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChild(TreeNode node, StringBuilder stringBuilder){
        if(node == null){
            return;
        }
        stringBuilder.append(node.val);
        // 判断结点左子树
        if(node.left != null){
            // 结点左孩子不为空
            stringBuilder.append("(");
            tree2strChild(node.left, stringBuilder);
            stringBuilder.append(")");
        }else{
            // 结点左孩子为空
            // 情况1：结点右孩子不为空
            if(node.right != null){
                stringBuilder.append("()");
            }else{
                // 情况2：结点右孩子为空
                return;
            }
        }
        // 判断结点右子树
        if(node.right == null){
            // 结点右孩子为空：直接返回
            return;
        }else{
            // 结点右孩子不为空：递归结点的右子树
            stringBuilder.append("(");
            tree2strChild(node.right, stringBuilder);
            stringBuilder.append(")");
        }
    }
}

12. 题目12：非递归实现二叉树前序遍历

题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

代码：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        TreeNode cur = root;   // 用于遍历二叉树
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                ret.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return ret;
    }
}

13. 题目13：非递归实现二叉树中序遍历

题目链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

代码：

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

14. 题目14：非递归实现二叉树后序遍历

题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

代码：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            // 后序遍历顺序为：根->左->右
            TreeNode top = stack.peek();  // 不可以直接pop栈顶元素
            // 当栈顶元素结点没有右子树时才可以打印根结点
            if(top.right == null || top.right == prev){
                ret.add(top.val);
                stack.pop();
                prev = top;
            }else{
                // 栈顶元素结点有右子树，优先遍历右子树后再打印根结点
                cur = top.right;
            }
        }
        return ret;
    }
}

到了这里，关于【数据结构】_8.二叉树OJ的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！