JAVA二叉树相关习题5

1. 二叉树前序非递归遍历实现。

. - 力扣（LeetCode）

递归的实现

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

与栈相结合

public void preOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}top = stack.pop();cur = top.right;}}

2. 二叉树中序非递归遍历实现。

. - 力扣（LeetCode）

3. 二叉树后序非递归遍历实现。

. - 力扣（LeetCode）

4. 检查两颗树是否相同。

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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.right, q.right)&&isSameTree(p.left, q.left);}
}

5. 另一颗树的子树。

. - 力扣（LeetCode）

//判断左数和其是否相同

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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){return false;}if(isSameTree(root,subRoot)){return true;}if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){return true;}return false;}
}

6.翻转二叉树。

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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;}
}

7. 判断一颗二叉树是否是平衡二叉树。

但是上述方式复杂度较高

上述代码速度很慢！！！

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int getHeight(TreeNode root) {if(root == null)return 0;int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);if(leftHeight>=0&&rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){return Math.max(leftHeight,rightHeight)+1;}else{return -1;}}public boolean isBalanced(TreeNode root) {if(root==null){return true;}return getHeight(root)>=0;}
}

8.对称二叉树。

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root==null){return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(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 isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left);}
}

9.二叉树的构建及遍历。

二叉树遍历_牛客题霸_牛客网

hasNext、hasNextLine、next、nextLine保姆级详解-CSDN博客

import java.util.Scanner;//从头到尾进行书写
class TreeNode{char val;TreeNode left;TreeNode right;//无参构造TreeNode(){}//有参构造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 处理多个 caseString 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);}
}

10.二叉树的分层遍历

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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()) {//求一下当前队列的大小  4int size = queue.size();//4List<Integer> tmp = new ArrayList<>();while (size != 0) {// 出队列4次 相当于把 这一层的节点都 出队了TreeNode cur = queue.poll();//System.out.print(cur.val+" ");tmp.add(cur.val);size--;//0if(cur.left != null) {queue.offer(cur.left);}if(cur.right != null) {queue.offer(cur.right);}}ret.add(tmp);}return ret;}
}

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

. - 力扣（LeetCode）

方法一：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
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;}}
}

方法二：与栈相结合

/*** 找到root 到 node 之间路径上 的 所有 的 节点 存储到stack中** @param root* @param node* @param stack* @return*/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 flg = getPath(root.left,node,stack);if(flg) {return true;}boolean flg2 = getPath(root.right,node,stack);if(flg2) {return true;}stack.pop();return false;}public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {if(root == null) {return null;}Stack<TreeNode> stackP = new Stack<>();Stack<TreeNode> stackQ = new Stack<>();getPath(root,p,stackP);getPath(root,q,stackQ);//对栈的操作int sizeP = stackP.size();int sizeQ = stackQ.size();if(sizeP > sizeQ) {int size = sizeP - sizeQ;while (size != 0) {stackP.pop();size--;}}else {int size = sizeQ - sizeP;while (size != 0) {stackQ.pop();size--;}}//两个栈当中 元素的个数是相同的while (!stackP.isEmpty() && !stackQ.isEmpty()) {if(stackP.peek() .equals(stackQ.peek())) {return stackP.peek();}stackP.pop();stackQ.pop();}return null;}

12. 根据一棵树的前序遍历与中序遍历构造二叉树。

. - 力扣（LeetCode）

先序遍历确定根，根据中序遍历确定左树和右树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int priIndex;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {//1. 没有左树 或者 没有右树了if(inbegin > inend) {return null;}//2.创建根节点TreeNode root = new TreeNode(preorder[priIndex]);//3.从中序遍历当中 找到根节点所在的下标int rootIndex = findIndex(inorder,inbegin,inend,preorder[priIndex]);if(rootIndex == -1) {return null;}priIndex++;//4. 创建左子树 和  右子树root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key) {for(int i = inbegin;i <= inend;i++) {if(inorder[i] == key) {return i;}}return -1;}}

13.根据一棵树的中序遍历与后序遍历构造二叉树

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/class Solution {public int postIndex ;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length-1;return buildTreeChild(postorder,inorder,0,inorder.length-1);}private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend) {//1. 没有左树 或者 没有右树了if(inbegin > inend) {return null;}//2.创建根节点TreeNode root = new TreeNode(postorder[postIndex]);//3.从中序遍历当中 找到根节点所在的下标int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);if(rootIndex == -1) {return null;}postIndex--;//4. 创建左子树 和  右子树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 i = inbegin;i <= inend;i++) {if(inorder[i] == key) {return i;}}return -1;}
}

14.二叉树创建字符串。

. - 力扣（LeetCode）

public String tree2str(TreeNode root) {StringBuilder stringBuilder  = new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}private void tree2strChild(TreeNode t,StringBuilder stringBuilder) {if(t == null) {return;}stringBuilder.append(t.val);if(t.left != null) {stringBuilder.append("(");tree2strChild(t.left,stringBuilder);stringBuilder.append(")");}else {if(t.right == null) {return;}else{stringBuilder.append("()");}}if(t.right != null) {stringBuilder.append("(");tree2strChild(t.right,stringBuilder);stringBuilder.append(")");}else {return;}}public void preOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}top = stack.pop();cur = top.right;}}public void inOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}top = stack.pop();System.out.print(top.val + " ");cur = top.right;}}