剑指offer二叉树专题

4.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例1
输入
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值
{1,2,5,3,4,6,7}

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length ==0 || in.length ==0) return null;
        return construct(pre,0,pre.length-1,in,0,in.length-1);
    }
    public TreeNode construct(int [] pre, int startpre,int endpre,int [] in,int startin, int endin){
        if(startin > endin || startpre > endpre) return null;
        TreeNode root = new TreeNode(pre[startpre]);
        for(int i=startin; i <=endin ;i++){
            if(pre[startpre] == in[i]){
                root.left = construct(pre,startpre+1,endpre-endin+i,in,startin,i-1);
                root.right = construct(pre,startpre-startin+i+1,endpre,in,i+1,endin);
            }
          }
        return root;
    }
}

17.输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
示例1
输入
{8,8,#,9,#,2,#,5},{8,9,#,2}
返回值
true

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false;
        if(root1 != null && root2 != null){
            if(root1.val == root2.val){
                result = istrue(root1,root2);
            }
            if(!result){
                result = HasSubtree(root1.left,root2);
            }
            if(!result){
                result = HasSubtree(root1.right,root2);
            }
        }
        return result;
        }
   public boolean istrue(TreeNode root1,TreeNode root2){
        if(root2 == null) return true;
        if(root1 == null) return false;
        if(root1.val != root2.val) return false;
        return istrue(root1.left,root2.left)&&istrue(root1.right,root2.right);
    }
}

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5

public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null) return;
        if(root.left == null && root.right == null) return;
       TreeNode trmp = root.left;
        root.left = root.right;
        root.right = trmp;
        if(root.left != null) Mirror(root.left);
        if(root.right != null) Mirror(root.right);
        
    }
    
}

22.从上往下打印出二叉树的每个节点，同层节点从左至右打印。
示例1
输入
复制
{5,4,#,3,#,2,#,1}
返回值
复制
[5,4,3,2,1]

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        Queue<TreeNode> queue = new ArrayList<>();
        ArrayList<Integer> pre = new ArrayList<>();
        if(root == null) return pre;
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            pre.add(root.val);
            if(root.left != null) queue.offer(root.left);
            if(root.right != null) queue.offer(root.right);
            
        }
        return pre;
    }
}

23.输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
示例1
输入
[4,8,6,12,16,14,10]
返回值
true

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence ==null || sequence.length == 0) return false;
        return issquencebst(0,sequence.length-1,sequence);
    }
    public boolean issquencebst(int start, int end, int [] sequence){
        int root = sequence[end];
        int mid = end-1;
        if(end <= start) return true;
        while(sequence[mid] > root){
            mid--;
            if(mid < start) return true;
        }
        for(int i= start; i <=mid; i++){
            if(sequence[i] > root) {
                return false;
            }
        }
        if(!issquencebst(start,mid,sequence)){
            return false;
        }
        if(!issquencebst(mid+1,end-1,sequence)){
            return false;
        }
        return true;
    }
}

24输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
示例1
输入
{10,5,12,4,7},22
返回值
[[10,5,7],[10,12]]

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> pre = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();
        if(root ==null) return pre;
        int sum =0;
        Path(root,target,sum,pre,path);
        return pre;        
    }
    
   public void Path(TreeNode root, int target,int sum, ArrayList<ArrayList<Integer>> pre, ArrayList<Integer> path){
       sum += root.val;
       path.add(root.val);
       if(root.left == null && root.right == null && sum == target){
           pre.add(new ArrayList<Integer>(path));
       }
       if(root.left != null){
           Path(root.left,target,sum,pre,path);
       }
       if(root.right != null){
           Path(root.right,target,sum,pre,path);
       }
           path.remove(path.size()-1);
           sum -= root.val;
   }
}

38.输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
示例1
输入
{1,2,3,4,5,#,6,#,#,7}
返回值
4
思路：max(左子树的深度，右子树的深度）+1；

思路：
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        int depth = 0;
        int realdepth = Integer.MIN_VALUE;
        while(root.left != null){
            TreeDepth(root.left);
            depth++;
            realdepth = Math.max(depth,realdepth);
        }
        depth = 0;
        while(root.right != null){
            TreeDepth(root.right);
            realdepth = Math.max(depth,realdepth);
        }
  
    return realdepth; 
    }
}
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return left >right ? left+1: right +1;
    }
}

39.输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
示例1
输入
{1,2,3,4,5,6,7}
返回值
true

//思路
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root ==null) return true;
        //左右两棵树的高度差绝对值不超过1
        int leftdepth = depth(root.left);
        int rightdepth = depth(root.right);
        if(rightdepth - leftdepth <= 1 || leftdepth - rightdepth <= 1){
            return true;
        }
        return false;
    }
    public int depth(TreeNode root){
        if(root == null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        return left > right ?left+1:right +1;
    }
}
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root ==null) return true;
        //左右两棵树的高度差绝对值不超过1
        int leftdepth = depth(root.left);
        int rightdepth = depth(root.right);
        int diff = leftdepth -rightdepth;
        if(diff > 1 || diff <-1){
            return false;
        }
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }
    public int depth(TreeNode root){
        if(root == null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        return left > right ?left+1:right +1;
    }
}

57.给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/思路
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null) return null;
        TreeLinkNode pre =pNode;
        ArrayList<Integer> list = new ArrayList<>();
        orderbst(pNode,list);
        
        }
        return 
    }
    public ArrayList<Integer> orderbst(TreeLinkNode root,ArrayList<Integer> list ){
        if(root == null) return null;
        orderbst(root.left);
        list.add(root.val);
        orderbst(root.right);
        return list;
    }
   
}
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null) return null;
        if(pNode.right != null){
            TreeLinkNode node = pNode.right;
            while(node.left != null){
                node = node.left;
            }
            return node;
        }else {
            if(pNode.next == null) return null;
            else if(pNode.next.left == pNode){
                  return pNode.next;
        }
        else{
            while(pNode.next != null && pNode.next.right == pNode){
               pNode = pNode.next;
            }
             return pNode.next;
        }
}
}
}

58.请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
{8,6,6,5,7,7,5}
true
示例2
{8,6,9,5,7,7,5}
false

public class Solution {
    boolean isSymmetrical(TreeNode root)
    {
        if(root == null ) return true;
        if(root.left == null && root.right == null) return true;
        if(root.left == root.right){
            return true;
        }
        return isSymmetrical(root.left) && isSymmetrical(root.right);
    }
    
}
public class Solution {
    boolean isSymmetrical(TreeNode root)
    {
      return  isTree(root,root);
    }
    public boolean isTree(TreeNode root,TreeNode root1){
        if(root == null && root1 == null) return true;
        if(root == null || root1 == null ) return false;
        if(root.val != root1.val ) return false;
        return isTree(root.left,root1.right) && isTree(root.right,root1.left);
    }
}

59.请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
示例1
输入
{8,6,10,5,7,9,11}
返回值
[[8],[10,6],[5,7,9,11]]

//思路
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> pre = new ArrayList<ArrayList<>>();
        Deque<TreeNode> stack = new ArrayList<>();
        stack.push(root);
        int depth = 1;
        if(!stack.isEmpty()){
            TreeNode node = root;
            if(depth %2 == 1 && node != null){
                Print(root.left);
                Print(root.right);
                pre.add(stack.pop());
                depth++;
            }else if(depth %2 == 0 %% node != null){
                Print(root.right);
                Print(root.left);
                pre.add(stack.pop());
                depth++;
            }
        }
        return pre;
    }

}
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> pre = new ArrayList<ArrayList<>>();
        Stack<TreeNode> stack = new Stack<>();
        Queue<TreeNode> queue = new ArrayList<>();
        queue.offer(root);
        int depth = 1;
        if(!queue.isEmpty()){
            ArrayList<Integer> res = new ArrayList<>();
            if(depth %2 == 1){
                int size = queue.size();
                for(int i=0; i < size; i++){
                    TreeNode node = queue.poll();
                    stack.push(node.val);
                    if(i == size-1){
                        while(!stack.empty()){
                            res.add(stack.pop().val);
                        }
                    }
                    if(root.left != null) queue.offer(root.left);
                    if(root.right != null) queue.offer(root.right);
                }
            }else {
                int size = queue.size();
                for(int i=0; i< queue.size();i++){
                    TreeNode node = queue.poll();
                    res.add(node.val);
                    if(root.left != null) queue.offer(root.left);
                    if(root.right != null) queue.offer(root.right);
            }
        }
            pre.add(res);
            depth++;
    }
        return pre;
   }

}

60.从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
示例1
输入
{8,6,10,5,7,9,11}
返回值
[[8],[6,10],[5,7,9,11]]

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<<Integer> > res = new ArrayList<ArrayList<Integer> >();
        Queue<TreeNode> queue = new ArrayList<>();
        if(root == null) return res;
        queue.offer(root);
        if(!queue.isEmpty()){
            TreeNode node = queue.poll();
            res.add(node.val);
            if(node.left != null) queue.offer(root.left);
            if(node.right != null) queue.offer(root.right);
        }
        return res;
    }
    
}

61.请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

1.String.split()方法，返回是一个数组：
　“.”和“|”都是转义字符，必须得加"\\";
　如果用“.”作为分隔的话，必须是如下写法：
String.split("\\."),这样才能正确的分隔开，不能用String.split(".");
如果用“|”作为分隔的话，必须是如下写法：
String.split("\\|"),这样才能正确的分隔开，不能用String.split("|");
2.Integer.parseInt("123");其实默认是调用了
int i =Integer.parseInt("123"，10); 其中10代表的默认是10进制
public class Solution {
    StringBuilder res = new StringBuilder();
    String Serialize(TreeNode root) {
        if(root == null){
            res.append("#,");
            return res.toString();
        }
        res.append(root.val +",");
        Serialize(root.left);
        Serialize(root.right);
        return res.toString();
  }
    int index = -1;
    TreeNode Deserialize(String str) {
        TreeNode root = new TreeNode(0);
        if(str ==null || str.length() == 0) return null;
        String[] val = str.split(",");
        root = DeserializeSplit(val);
        return root;
  }
    public TreeNode DeserializeSplit(String[] val){
        index++;
        if(!val[index].equals("#")){
            TreeNode root = new TreeNode(Integer.parseInt(val[index]));
            root.left = DeserializeSplit(val);
            root.right = DeserializeSplit(val);
            return root;
        }
        return null;
    }
}

62.给定一棵二叉搜索树，请找出其中的第k小的结点。
示例1
输入
{5,3,7,2,4,6,8},3
返回值{4}
按结点数值大小顺序第三小结点的值为4

二叉树的中序遍历会得到一个递增的序列，因此在二叉搜索树里中序遍历比较常用
//思路
public class Solution {
    TreeNode KthNode(TreeNode root, int k)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        orderdfs(root,res);
        int [] pre = res.toList();
        for(int i = 0;i < pre.size();i++){
            if(i == k-1){
                return pre[i];
            }
        }
        return;
    }
    public ArrayList<Integer> orderdfs(TreeNode root,ArrayList<Integer> res){
        if(root == null) return res;
        if(root.left != null) orderdfs(root.left);
        res.add(root.val);
        if(root.right != null) orderdfs(root.right);
        return res;
    }
}
public class Solution {
    TreeNode res;
    int count =0;
    TreeNode KthNode(TreeNode root, int k)
    {
        orderdfs(root,k);
        return res;
    }
    public void orderdfs(TreeNode root,int k){
        
        if(root == null || count > k){
            return;
        }
        orderdfs(root.left,k);
        count++;
        if(count == k){
            res = root;
        }
        orderdfs(root.right,k);
    }
}

本文地址：https://blog.csdn.net/weixin_46640232/article/details/109645994