二叉树题目总结(Java版本)
程序员文章站
2022-05-20 21:34:34
...
二叉树总结
1. 重建二叉树
import java.util.*;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0||in.length == 0){
return null;
}
int curNode = pre[0];
TreeNode node = new TreeNode(curNode);
// 遍历数组,找到父节点在中序中的位置
// 递归的时候考虑终止条件,当前函数中的操作,如何递,归什么回去,归回去的赋值给谁
for(int i=0; i<in.length; i++){
if(in[i]==pre[0]){
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
node.right =reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),Arrays.copyOfRange(in, i+1, in.length));
}
}
return node;
}
}
2. 树的子结构
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean found = false;
if(root2==null||root1==null) return false;
// 首先找到开始的点
if(root1.val==root2.val) found = StartSearch(root1, root2);
if(!found){
found = (HasSubtree(root1.left, root2)||HasSubtree(root1.right, root2));
}
return found;
}
public boolean StartSearch(TreeNode root1, TreeNode root2){
// 不管原树节点为不为空,都返回true
if(root2==null) return true;
// 如果原树已经空了,但子树没空,则返回false
if(root1==null&&root2!=null) return false;
// 如果两个值不相等,则返回false
if(root1.val!=root2.val) return false;
return StartSearch(root1.left, root2.left)&&StartSearch(root1.right, root2.right);
}
}
3. 二叉树的镜像
public class Solution {
public void Mirror(TreeNode root) {
// 只需要递,不需要归
if(root==null) return;
exchange(root);
Mirror(root.left);
Mirror(root.right);
}
public void exchange(TreeNode root){
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
4. 从上到下打印二叉树
import java.util.*;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result = new ArrayList<> ();
Queue<TreeNode> queue = new LinkedList<> ();
if(root==null) return result;
queue.add(root);
while(!queue.isEmpty()){
TreeNode current = queue.poll();
result.add(current.val);
if(current.left!=null) queue.add(current.left);
if(current.right!=null) queue.add(current.right);
}
return result;
}
}
5. 二叉搜索树的后序遍历
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length==0) return false;
if(sequence.length==1) return true;
// 开始递归
return Check(sequence, 0, sequence.length-1);
}
// 找到左子树,判断左子树的所有结点是否小于根节点
public boolean Check(int[] sequence, int start, int end){
// 终止条件
if(end<=start) return true;
int root = sequence[end];
int p = end-1;
// 左子树最后一个结点
while(p>=start&&sequence[p]>root){
p--;
}
// 一旦左子树有结点小于根节点,返回false
for(int i=start; i<=p; i++){
if(sequence[i]>root) return false;
}
// 搜索左右子树
return Check(sequence, p+1, end-1)&&Check(sequence, start, p);
}
}
6. 二叉树中和为某一值的路径
import java.util.ArrayList;
public class Solution {
// 设为全局变量比较简洁
ArrayList<ArrayList<Integer>> result = new ArrayList<> ();
ArrayList<Integer> temp = new ArrayList<Integer> ();
// root为入口点,开始回溯
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
int sum = 0;
if(root==null) return result;
backChecking(root, target, sum);
return result;
}
// 回溯递归函数
public void backChecking(TreeNode root, int target, int sum){
if(root==null) {
return;
}
sum += root.val;
temp.add(root.val);
// 添加条件,如果root==null再添加,那么可能会重复添加值到结果中
if(root.left==null&&root.right==null&&sum==target){
result.add(new ArrayList<Integer>(temp));
}
backChecking(root.left, target, sum);
backChecking(root.right, target, sum);
temp.remove(temp.size()-1);
}
}
7. 二叉树的深度:递归和非递归版本
非递归
public class Solution {
int count = 0;
public int TreeDepth(TreeNode root) {
if(root==null) return 0;
return Math.max(TreeDepth(root.left), TreeDepth(root.right))+1;
}
}
递归
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
int count = 0;
// 重点是这儿,记录同一层的个数
int nextCount = 1;
int depth = 0;
queue.add(root);
while(!queue.isEmpty()){
TreeNode top = queue.poll();
count++;
if(top.left!=null){
queue.add(top.left);
}
if(top.right!=null){
queue.add(top.right);
}
if(count==nextCount){
nextCount = queue.size();
count = 0;
depth++;
}
}
return depth;
}
}
8.平衡二叉树:后序和先序遍历
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null) return true;
int l = 0;
int r = 0;
if(root.left!=null){
l = getDepth(root.left);
}
if(root.right!=null){
r = getDepth(root.right);
}
if(l-r>1||r-l>1) return false;
// 只要有一个false出现,则会返回false
return IsBalanced_Solution(root.left)&IsBalanced_Solution(root.right);
}
public int getDepth(TreeNode root){
if(root==null) return 0;
return Math.max(getDepth(root.right), getDepth(root.left))+1;
}
}
9. 二叉树的下一个结点
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode==null) return null;
// 首先判断有没有右结点,有的话得找右结点最左边的结点
if(pNode.right!=null){
pNode = pNode.right;
while(pNode.left!=null){
pNode = pNode.left;
}
return pNode;
}
// 如果没有,则向上找到第一个左节点
else{
while(pNode.next!=null){
if(pNode==pNode.next.left){
return pNode.next;
}
pNode = pNode.next;
}
// 如果找到根节点都没有找到,返回null
return null;
}
}
}
10.对称的二叉树
与是否是子树问题有点像
public class Solution {
public boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot==null){
return true;
}
return Search(pRoot.left, pRoot.right);
}
public boolean Search(TreeNode node1, TreeNode node2){
if(node1==null&&node2!=null) return false;
if(node1!=null&&node2==null) return false;
if(node1==null&&node2==null) return true;
if(node1.val!=node2.val) return false;
return Search(node1.left, node2.right)&&Search(node1.right, node2.left);
}
}
11. 按之字形打印二叉树
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
//首先按层遍历所有节点
//先把根节点存到栈中,然后会出栈,然后记录左右节点,把左右当到第二个栈中,那么右先推出来,存右子节点,然后左节点到第一个栈。
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(pRoot==null) return result;
Stack<TreeNode> stack1=new Stack<>();
Stack<TreeNode> stack2=new Stack<>();
stack1.push(pRoot);
while(!stack1.isEmpty()||!stack2.isEmpty()){
ArrayList<Integer> temp = new ArrayList<Integer>();
if(!stack2.isEmpty()){
while(!stack2.isEmpty()){
TreeNode node = stack2.pop();
temp.add(node.val);
if(node.right!=null) stack1.push(node.right);
if(node.left!=null) stack1.push(node.left);
}
}
else{
while(!stack1.isEmpty()){
TreeNode node = stack1.pop();
temp.add(node.val);
if(node.left!=null) stack2.push(node.left);
if(node.right!=null) stack2.push(node.right);
}
}
result.add(new ArrayList<Integer>(temp));
}
return result;
}
}
12. 把二叉树打印多行
与求二叉树深度类似
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(pRoot==null) return result;
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<Integer>();
int count = 0;
int size = 1;
queue.add(pRoot);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
list.add(node.val);
count++;
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
if(count==size){
size = queue.size();
count = 0;
result.add(new ArrayList<Integer>(list));
list = new ArrayList<Integer>();
}
}
return result;
}
}
13. 序列化二叉树
public class Solution {
int index=0;
StringBuilder builder = new StringBuilder();
String Serialize(TreeNode root) {
if(root!=null) builder.append(root.val+"!");
else{
return builder.append("#!").toString();
}
Serialize(root.left);
Serialize(root.right);
return builder.toString();
}
TreeNode Deserialize(String str) {
if(str==null) return null;
String[] nodes=str.split("!");
if(index>=nodes.length) return null;
if(nodes[index].equals("#")){
index++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(nodes[index++]));
node.left = Deserialize(str);
node.right = Deserialize(str);
return node;
}
}
14. 求第K小的数
递归
public class Solution {
int index = 0; //计数器
TreeNode KthNode(TreeNode root, int k)
{
if(root != null){ //中序遍历寻找第k个
TreeNode node = KthNode(root.left,k);
// 如果这两行去掉,我们仍然能找到第K大的数,但是没法return, 所以要想办法return
if(node != null)
return node;
index ++;
if(index == k)
return root;
node = KthNode(root.right,k);
if(node != null)
return node;
}
return null;
}
}
非递归
import java.util.*;
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k)
{ int index = 0;
Stack<TreeNode> stack = new Stack<>();
while(pRoot!=null||!stack.isEmpty()){
while(pRoot!=null){
stack.push(pRoot);
pRoot = pRoot.left;
}
if(!stack.isEmpty()){
pRoot = stack.pop();
index++;
if(index==k) return pRoot;
pRoot = pRoot.right;
}
}
return null;
}
}
15. 先序, 中序, 后序的非递归实现
先序
public void midOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack = new Stack<>();
// 当当前节点为空,且stack为空时不能进入循环
while(Node != null || !stack.empty())
{
while (Node != null)
{ System.out.println(Node.val);
stack.push(Node);
Node = Node.left;
}
if(!stack.empty())
{
Node = stack.pop();
System.out.print(Node.element + " ");
Node = Node.right;
}
}
}
中序
public void midOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack = new Stack<>();
// 当当前节点为空,且stack为空时不能进入循环
while(Node != null || !stack.empty())
{
while (Node != null)
{ System.out.println(Node.val);
stack.push(Node);
Node = Node.left;
}
if(!stack.empty())
{
Node = stack.pop();
System.out.print(Node.element + " ");
Node = Node.right;
}
}
}
后序
public void posOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
int i = 1;
while(Node != null || !stack1.empty())
{
while (Node != null)
{
stack1.push(Node);
stack2.push(0);
Node = Node.left;
}
while(!stack1.empty() && stack2.peek() == i)
{
stack2.pop();
System.out.print(stack1.pop().element + " ");
}
if(!stack1.empty())
{
stack2.pop();
stack2.push(1);
Node = stack1.peek();
Node = Node.right;
}
}
}