知识改变命运数据结构【二叉树OJ题】

用户11319080

发布于 2024-10-17 19:17:27

5300

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

1. 检查两颗树是否相同OJ链接

 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;
            }
            boolean left=isSameTree(p.left,q.left);
            boolean right=isSameTree(p.right,q.right);
            if (left&&right) {
                return true;
            } else {
                return false;
            }

        }
 }

2. 另一颗树的子树。OJ链接

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;
            }
            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 (root==null&&subRoot==null) {
                return true;
            }
            if(isSameTree(root,subRoot)) {
                return true;
            }
            if(isSubtree(root.left,subRoot)) {
                return true;
            }
            if (isSubtree(root.right,subRoot)) {
                return true;
            }
            return false;
        }
}

3. 翻转二叉树。Oj链接

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

4. 判断一颗二叉树是否是平衡二叉树。OJ链接

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

5. 对称二叉树。OJ链接

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

6. 二叉树的构建及遍历。OJ链接

public class Main {
    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public static int i = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String ch = in.nextLine();
            TreeNode root = creatTree(ch);
            inOrder(root);
        }
    }
    public static TreeNode creatTree(String ch) {
        TreeNode root = null;

        char ch2 = ch.charAt(i);
        if (ch2 != '#') {
            root = new TreeNode(ch2);
            i++;
            root.left = creatTree(ch);
            root.right = creatTree(ch);
        } 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);
    }
}

7. 二叉树的分层遍历。OJ链接

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List <List<Integer>> ret =new LinkedList<>();
        if(root==null) {
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> list=new ArrayList<>();
            int size=queue.size();
            while(size!=0) {
                TreeNode cur=queue.poll();
                size--;
                list.add(cur.val);
                if(cur.left!=null) {
                    queue.offer(cur.left);
                }
                if(cur.right!=null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }
}

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

方法1：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) {
            return null;
        }
        if(root==p) {
            return p;
        }
        if(root==q) {
            return q;
        }
        TreeNode leftRoot=lowestCommonAncestor(root.left,p,q);
        TreeNode rightRoot=lowestCommonAncestor(root.right,p,q);
        if(leftRoot!=null&&rightRoot!=null) {
            return root;
        }
        if(leftRoot==null) {
            return rightRoot;
        }
        if(rightRoot==null) {
            return leftRoot;
        }
        return null;
    }
}

9. 根据一棵树的前序遍历与中序遍历构造二叉树。 OJ链接

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

10. 根据一棵树的中序遍历与后序遍历构造二叉树。OJ链接

11. 二叉树创建字符串。OJ链接

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder=new StringBuilder();
        GreatString(stringBuilder,root);
        return stringBuilder.toString();
    }
    public void GreatString(StringBuilder stringBuilder,TreeNode root) {
        if(root==null) {
            return;
        }
        stringBuilder.append(root.val);
        if (root.left!=null) {
            stringBuilder.append("(");
            GreatString(stringBuilder,root.left);
            stringBuilder.append(")");
        } else {
            if(root.right==null) {
                return;
            } else {
                stringBuilder.append("()");
            }
        }
        if(root.right!=null) {
            stringBuilder.append("(");
            GreatString(stringBuilder,root.right);
            stringBuilder.append(")");
        } else {
            return;
        }
    }
}

12. 二叉树前序非递归遍历实现。OJ链接

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

13. 二叉树中序非递归遍历实现。OJ链接

class Solution {
   
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        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;
            }
            cur = stack.pop();
            ret.add(cur.val);
            cur = cur.right;
        } 
        return ret;
    }
}

14. 二叉树后序非递归遍历实现。`[OJ链接](https://leetcode.cn/problems/binary-tree-postorder-traversal/)`

class Solution {
 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode pre=null;
        while (cur!=null||!stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                //ret.add(cur.val);
                cur = cur.left;
            }
         TreeNode top = stack.peek();
            if(top.right==null||top.right==pre) {
                stack.pop();
                ret.add(top.val);
                pre=top;
            } else {
                cur=top.right;
            }
        }
        return ret;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-27，如有侵权请联系 cloudcommunity@tencent.com 删除

root

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

知识改变命运数据结构【二叉树OJ题】

知识改变命运数据结构【二叉树OJ题】

1. 检查两颗树是否相同OJ链接

2. 另一颗树的子树。OJ链接

3. 翻转二叉树。Oj链接

4. 判断一颗二叉树是否是平衡二叉树。OJ链接

5. 对称二叉树。OJ链接

6. 二叉树的构建及遍历。OJ链接

7. 二叉树的分层遍历。OJ链接

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

9. 根据一棵树的前序遍历与中序遍历构造二叉树。 OJ链接

10. 根据一棵树的中序遍历与后序遍历构造二叉树。OJ链接

11. 二叉树创建字符串。OJ链接

12. 二叉树前序非递归遍历实现。OJ链接

13. 二叉树中序非递归遍历实现。OJ链接

14. 二叉树后序非递归遍历实现。`[OJ链接](https://leetcode.cn/problems/binary-tree-postorder-traversal/)`

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

知识改变命运 数据结构【二叉树OJ题】

知识改变命运 数据结构【二叉树OJ题】

1. 检查两颗树是否相同OJ链接

2. 另一颗树的子树。OJ链接

3. 翻转二叉树。Oj链接

4. 判断一颗二叉树是否是平衡二叉树。OJ链接

5. 对称二叉树。OJ链接

6. 二叉树的构建及遍历。OJ链接

7. 二叉树的分层遍历 。OJ链接

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

9. 根据一棵树的前序遍历与中序遍历构造二叉树。 OJ链接

10. 根据一棵树的中序遍历与后序遍历构造二叉树。OJ链接

11. 二叉树创建字符串。OJ链接

12. 二叉树前序非递归遍历实现 。OJ链接

13. 二叉树中序非递归遍历实现。OJ链接

14. 二叉树后序非递归遍历实现。[OJ链接](https://leetcode.cn/problems/binary-tree-postorder-traversal/)

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

知识改变命运数据结构【二叉树OJ题】

知识改变命运数据结构【二叉树OJ题】

7. 二叉树的分层遍历。OJ链接

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

12. 二叉树前序非递归遍历实现。OJ链接

14. 二叉树后序非递归遍历实现。`[OJ链接](https://leetcode.cn/problems/binary-tree-postorder-traversal/)`