炽乐清网站建设,网站建设与运营方案,部署个人网站,中介网站建设数据结构 二叉树OJ题 文章目录 数据结构 二叉树OJ题1. 检查两颗二叉树是否相同2. 判断树是否为另一个树的子树3. 翻转二叉树4. 平衡二叉树5. 对称二叉树6. 二叉树遍历7. 二叉树层序遍历8. 最近公共祖先9. 二叉树创建字符串10. 非递归方式实现前序遍历11. 非递归方式实现中序遍历…数据结构 二叉树OJ题 文章目录 数据结构 二叉树OJ题1. 检查两颗二叉树是否相同2. 判断树是否为另一个树的子树3. 翻转二叉树4. 平衡二叉树5. 对称二叉树6. 二叉树遍历7. 二叉树层序遍历8. 最近公共祖先9. 二叉树创建字符串10. 非递归方式实现前序遍历11. 非递归方式实现中序遍历12. 非递归方式实现后序遍历 结合之前所学的二叉树知识我们来刷一些OJ题巩固一下 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;}return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}
}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 (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;}if (root.left null root.right null) {return root;}TreeNode temp root.left;root.left root.right;root.right temp;invertTree(root.left);invertTree(root.right);return root;}
}4. 平衡二叉树
OJ链接
代码示例
class Solution {public boolean isBalanced(TreeNode root) {if (root null) {return true;}int leftH getHeight(root.left);int rightH getHeight(root.right);if (Math.abs(leftH-rightH) 1) {return false;}return isBalanced(root.left) isBalanced(root.right);}public int getHeight(TreeNode root) {if (root null) {return 0;}int leftNode getHeight(root.left);int rightNode getHeight(root.right);return leftNode rightNode ? leftNode 1 : rightNode 1;}
}5. 对称二叉树
OJ链接
代码示例
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) {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. 二叉树遍历
[OJ链接]:
代码示例
import java.util.Scanner;public class Main {public static int i 0;static class TreeNode {char val;TreeNode left;TreeNode right;public TreeNode(char val) {this.val val;}}public static void main(String[] args) {Scanner in new Scanner(System.in);String s1 in.nextLine();TreeNode root createTree(s1);isOrder(root);}public static TreeNode createTree(String s) {if (s.charAt(i) ! #) {TreeNode root new TreeNode(s.charAt(i));i;root.left createTree(s);root.right createTree(s);return root;}else {i;}return null;}public static void isOrder(TreeNode root) {if (root null) {return;}isOrder(root.left);System.out.print(root.val );isOrder(root.right);}
}7. 二叉树层序遍历
OJ链接
代码示例
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger ret1 new LinkedList();QueueTreeNode queue new LinkedList();if (root null) {return ret1;}queue.offer(root);while(!queue.isEmpty()) {ListInteger list new LinkedList();int size queue.size();while(size ! 0) {TreeNode cur queue.poll();size--;System.out.print(cur.val );if (cur.left ! null) {queue.offer(cur.left);}if (cur.right ! null) {queue.offer(cur.right);}list.add(cur.val);}ret1.add(list);}return ret1;}
}8. 最近公共祖先
OJ链接
代码示例
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null) {return null;}if (root p || root q) {return root;}TreeNode leftTree lowestCommonAncestor(root.left,p,q);TreeNode rightTree lowestCommonAncestor(root.right,p,q);if (leftTree ! null rightTree ! null) {return root;}else if(leftTree ! null) {return leftTree;}else {return rightTree;}}
}9. 二叉树创建字符串
[OJ链接]:
代码示例
class Solution {public String tree2str(TreeNode root) {StringBuilder stringBuilder new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}private void tree2strChild(TreeNode root, StringBuilder stringBuilder) {if (root null) {return;}stringBuilder.append(root.val );if (root.left ! null) {stringBuilder.append(();tree2strChild(root.left,stringBuilder);stringBuilder.append());}else {if (root.right null) {return;}else{stringBuilder.append(());}}if (root.right ! null) {stringBuilder.append(();tree2strChild(root.right,stringBuilder);stringBuilder.append());}else {return;}}
} 10. 非递归方式实现前序遍历
[OJ链接]:
代码示例
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger list new LinkedList();if (root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()) {while(cur ! null) {stack.push(cur);list.add(cur.val);cur cur.left;}TreeNode top stack.pop();cur top.right;}return list;}}11. 非递归方式实现中序遍历
[OJ链接]:
代码示例
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger list new LinkedList();if (root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.empty()) {while(cur ! null) {stack.push(cur);cur cur.left;}TreeNode top stack.pop();list.add(top.val);cur top.right;}return list;}
}12. 非递归方式实现后序遍历
[OJ链接]:
代码示例
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger list new LinkedList();if (root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode prev null;while(cur ! null || !stack.isEmpty()) {while(cur ! null) {stack.push(cur);cur cur.left;}TreeNode top stack.peek();if (top.right null || top.right prev) {list.add(top.val);stack.pop();prev top; // 记录下最新被打印的节点}else {cur top.right;}}return list;}
}
