剑指-树

感谢K神

重建二叉树

根据前序遍历和后续遍历的结果重建二叉树。
思路：通过前序遍历的结果找到根节点，在后续遍历结果中分割树的左子树和右子树
难点：区间如何划分

//使用HashMap更快速的定位到节点在中序遍历的位置
    HashMap<Integer,Integer> inMaps = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
      //为空判断
      for(int i = 0;i<inorder.length;i++)
      {
          inMaps.put(inorder[i],i);
      }
      return construct(preorder,0,0,inorder.length-1);
    }
    public TreeNode construct(int[] preorder,int root,int in_l,int in_r)
    {
        if(in_l>in_r) return null;
        //找到根节点的值
        int value = preorder[root];
        //新建节点
        TreeNode node = new TreeNode(value);
        //找到中序的位置
        int in_index = inMaps.get(value);
        //递归
/**
左子树的根节点为前一步加1
在中序遍历的起始位置为当前中序遍历的起始位置
在中序遍历的终止位置为当前根节点在中序遍历的位置-1
**/
        node.left = construct(preorder,root+1,in_l,in_index-1);
/**
右子树的根节点为前一步加1加上左子树的长度（in_index-in_l）
右子树在中序遍历的起始位置为当前in_index+1
右子树在中序遍历的终止位置为in_r
**/
        node.right = construct(preorder,root+in_index-in_l+1,in_index+1,in_r);
        return node;
    }

拓展：中序和后序也可以构成二叉树

剑指 Offer 26. 树的子结构

思路：如何定义子结构是相等的
1：如果当前两个节点的值是相等的，那么就递归两者的左和右，直到一方为空，或者两方皆空的时候，再判断。
2：两个节点的值不等，false

   public boolean isSubStructure(TreeNode A, TreeNode B) {
        //判断左子树是不是，右子树是不是
        boolean result = false;

        if(A!=null && B!=null){
            if(A.val == B.val) result = isSubTree(A,B);
            if(!result)
            result = isSubStructure(A.left,B);
            if(!result)
            result = isSubStructure(A.right,B);
        }
        return result;
    }

    public boolean isSubTree(TreeNode A ,TreeNode B)
    {
        if(A==null && B==null) return true;
        if(A!=null && B == null) return true;
        if(A==null && B!=null) return false;
        if(A.val != B.val) return false;
        return isSubTree(A.left,B.left) && isSubTree(A.right,B.right);
    }

二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

image.png

思路：翻转二叉树，反转子树的二叉树，只有后序遍历可以操纵左右节点
非递归：

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
//交换指向
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

对称的二叉树

剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

public boolean isSame(TreeNode L,TreeNode R)
{
    if(L==null && R == null) return true;
    if(L==null && R == null) return false;
    if(L.val != R.val) return false;
    return isSame(L.left,R.right) && isSame(L.right,R.left);
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

重点在于确定奇偶

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
                else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

剑指 Offer 37. 序列化二叉树

public class Codec {
//序列化，传入二叉树，输出层序遍历结果，null也得输出
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
//移除最后一个,号
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
//空判断
        if(data.equals("[]")) return null;
//由,号分割，并且[,和]都移除了，目前val里面都是值和null
        String[] vals = data.substring(1, data.length() - 1).split(",");
//建立根节点
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
//根节点入队列
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
//i用来遍历字符串数组
        int i = 1;
        while(!queue.isEmpty()) {
//取出根节点
            TreeNode node = queue.poll();
//获取当前根节点的左节点，不为空的话，就左指向，并且加入队列
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
//，右节点，同上
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点

二叉搜索树的中序遍历是底层序列，所以先把中序遍历的结果保存到list里面，然后取出第size-k个就好了

剑指 Offer 55 - I. 二叉树的深度

    public int maxDepth(TreeNode root) {
        return root==null?0:depth(root);
    }
    public int depth(TreeNode node)
    {
        if(node == null) return 0;
        return Math.max(depth(node.left),depth(node.right))+1;
    }

剑指 Offer 55 - II. 平衡二叉树

判断当前节点的左深度-右深度的绝对值是否超过1 ，不超过就递归再看左和右

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int depth(TreeNode node)
    {
        if(node == null) return 0;
        return Math.max(depth(node.left),depth(node.right))+1;
    }
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         while(root != null) {
            if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}

剑指 Offer 68 - II. 二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null; // 如果树为空，直接返回null
        if(root == p || root == q) return root; // 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
        TreeNode left = lowestCommonAncestor(root.left, p, q); // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
        TreeNode right = lowestCommonAncestor(root.right, p, q); // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
        if(left == null) return right; // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        else if(right == null) return left; // 否则，如果 left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况，如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        else return root; //否则，当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
    }
}

面试题34. 二叉树中和为某一值的路径

class Solution {
//记录结果
    LinkedList<List<Integer>> res = new LinkedList<>();
//记录路径
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
//保证是到叶节点的
        if(tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
//采用先序遍历
        recur(root.left, tar);
        recur(root.right, tar);
//移除最后加入的
        path.removeLast();
    }
}