【数据结构】_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）

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

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

代码：

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 处理多个 casei=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;}
}