剑指-树

时间:2021-6-4 作者:qvyue

感谢K神

重建二叉树

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

//使用HashMap更快速的定位到节点在中序遍历的位置
    HashMap inMaps = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
      //为空判断
      for(int i = 0;iin_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 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> levelOrder(TreeNode root) {
        Queue queue = new LinkedList();
        List> res = new ArrayList();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList 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 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 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))

剑指 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.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> res = new LinkedList();
//记录路径
    LinkedList path = new LinkedList(); 
    public List> 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();
    }
}
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。