剑指offer 二叉树专题

二叉树的定义及相关性质

二叉树性质及操作

注意:对于String来说,length()是一个方法,必须加括号
而对于数组来说,length只是数组的父类Array从Object哪里继承过来的属性,所以是类的属性,就不需要加括号

剑指offer 07 重建二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;   //将preorder 变成全局变量, recur中可直接调用

        //将inorder装入HashMap中,方便后面查找root
        for(int i=0; i<inorder.length; i++){
            dic.put(inorder[i],i);
        }
        return recur(0,0,inorder.length - 1);
    }
    /**
    * 利用inorder的最左和最右node分别在list中的第一和最后一个,不断地迭代遍历整个树
    * @param root_preIndx root在preorder中的index
    * @param left_inIndx  整个树的最左node在inorder中的index
    * @param right_inIndx 整个树的最右node在inorder中的index
    * @return 当前树的root
    */
    public TreeNode recur (int root_preIndx, int left_inIndx, int right_inIndx){
        //当最左node的index大于最右node的index, 即已经遍历完
        if(left_inIndx > right_inIndx){
            return null; 
        }

        TreeNode node = new TreeNode(preorder[root_preIndx]);
        int root_inIndx = dic.get(preorder[root_preIndx]);  //查询root在inorder中的index
        //node.left = 左子树的root
        node.left = recur(root_preIndx + 1, left_inIndx, root_inIndx - 1);

        //求出左子树在inorder中长度len_left,node.right在preorder中的index = root_preIndx + len_left
        int len_left = root_inIndx - left_inIndx + 1;
        node.right = recur(root_preIndx + len_left, root_inIndx + 1, right_inIndx);

        return node;
    }
}

剑指offer 26 树的子结构
若树B是树A的子结构,树A节点为M,树B节点为N, 则
时间复杂度O(MN)
空间复杂度O(M)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        if (treeCompare(A,B)) return true;
        else return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

//开始对比子树
    public boolean treeCompare(TreeNode A, TreeNode B){
        // 第一次是不会进来,因为上面调用条件是A,B同时不为null
        // 之后再进来的前提则是A,B root 相同,对比child
        if (B == null) return true;

        //如果B == null 且 A != null 说明B 没结束但A结束了 则肯定为false
        if (A == null) return false;

        if (A.val == B.val){
            return treeCompare(A.left,B.left) && treeCompare(A.right,B.right);
        }
        else return false;    
    }
}

剑指offer 27 二叉树的镜像
时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        // 暂存左子树
        TreeNode temp = root.left;
        // 递归
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        //当无子节点时,返回节点本身
        return root;
    }
}

剑指offer 28 对称的二叉树
时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isEqual(mirrorTree(root.right),root.left);
        }

    public TreeNode mirrorTree(TreeNode root){
        if(root == null) return null;
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
    }

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

剑指offer 32 从上到下打印二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        // 注意:LinkedList,双大写
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.add(root);

        //注意:isEmpty()
        while(!queue.isEmpty()){
           TreeNode node = queue.poll();
           list.add(node.val);
           if(node.left != null) queue.add(node.left);
           if(node.right != null) queue.add(node.right);
        }
        int[] ans = new int[list.size()];
        // 括号之间用“;”隔开
        for(int i = 0; i<list.size(); i++){
            ans[i] = list.get(i);
        }

        return ans;
    }
}

剑指offer 32-ii 从上到下打印二叉树 ii

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        // 当root为null是,List也为null

        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();

            //注意:此时应从queue的size开始递减,size为0时,queue为空
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }

            ans.add(temp);
        }

        return ans;
    }
}

剑指offer 32-iii 从上到下打印二叉树 iii
基本思路: queue的存储顺序不变,根据奇偶行,在组temp时进行前插或顺序排列,进而达到改变偶行读取顺序

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        int level = 1;

        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            LinkedList<Integer> temp = new LinkedList<>();
            int rem = level % 2;

            if(rem == 0){
                for(int i = queue.size(); i>0; i--){
                    TreeNode node = queue.poll();
                    // 偶行 从右至左
                    temp.addFirst(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);  
                }
            }
            else{
                for(int i = queue.size(); i>0; i--){
                    TreeNode node = queue.poll();
                    temp.add(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                }
            }
            ans.add(temp);
            level++;
        }
        return ans;
    }
}

剑指offer 33 二叉搜索树的后序遍历序列
基本思路:1.数列中最后一位是root
     2.从左至右找出第一个比root大的node,位置记作temp(之后为右子树,之前为左子树)
     3. temp之后若出现小于root,则为false

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        // 数组 length不需要括号
        return orderCheck(postorder, 0, postorder.length-1);
    }

    public boolean orderCheck(int[] postorder, int left, int right){
        // 需要先判断left 和 right 大小关系,否则会超出范围
        if(left >= right) return true;
        int root = postorder[right];
        int firstLarge = left;

        // 找第一个大于root的节点
        while(postorder[firstLarge] < root){
            firstLarge++;
        }

        // 判断之后是否都大于root
        for(int temp = firstLarge; temp < right; temp++){
            if(postorder[temp] < root) return false;
        }
        
        return orderCheck(postorder, left, firstLarge-1) && orderCheck(postorder, firstLarge, right-1);
        
    }
}

剑指offer 34 二叉树中和为某一值的路径
经典回溯问题

/**
 * 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>> ans = new ArrayList<>();
    public LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        helper(root,sum);
        return ans;
    }

    //返回类型是void 空型 这里面如果return语句返回一个值的话会报错,
    //如果就只是一个return;表示程序结束不继续往下执行。
    public void helper(TreeNode root, int sum){
        if(root == null) return;
        sum -= root.val;
        list.add(root.val);

        if(root.left == null && root.right == null && sum == 0){
            // 值得注意的是,记录路径时若直接执行 ans.add(list) 则是将 list 对象加入了 ans ;
            //后续 list 改变时 ans 中的 list 对象也会随之改变。
            //正确做法:ans.add(new ArrayList(list)) 相当于复制了一个 list 并加入到 ans
            ans.add(new ArrayList<>(list));
            // 这里不加remove和return的目的是,接下来的子node都是null,下一步自动return

        }
        helper(root.left,sum);
        helper(root.right,sum);
        // remove目的是不改变 public list
        list.removeLast();
    }
}

剑指offer 55i 二叉树的深度
第一个完全一次作对的题目 :) 加油,别放弃

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

剑指offer 55ii 平衡二叉树

当左右平衡但子树不平衡时

讨论思考:如上图所示,该题不仅要思考总树是否平衡,也要考虑子树是否平衡
不可以理所当然认为getDeepth由于迭代,会在node 2时返回 -1,从而省去
if(rightDeepth == -1 || leftDeepth == -1) return -1;
事实上,在node 2时,确实会返回-1,但此时函数并未完成,即并未回归到node 1,故getDeepth(root)时,会返回Math.max(2,2)而非Math.max(3,3),所以最后仍不会得出正确答案。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        if(getDeepth(root) == -1) return false;
        return true;
    }
    public int getDeepth(TreeNode root){
        if(root == null) return 0;
        int leftDeepth = getDeepth(root.left);
        int rightDeepth = getDeepth(root.right);
        // 计算root的左右两边是否高度差是否大于1
        if(Math.abs(leftDeepth - rightDeepth) > 1) return -1;
        // 计算 左右子树 的高度差是否大于1
        if(rightDeepth == -1 || leftDeepth == -1) return -1;
        
        return Math.max(leftDeepth,rightDeepth) + 1;
    }
}

剑指offer 37 序列化二叉树
第一次挑战困难的题,能够读懂并且写明了。 又进了一步,加油 :)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    TreeNode node;
    // Encodes a tree to a single string.
    // 虽然可以直接拼接字符串,但是,在循环中,每次循环都会创建新的字符串对象,
    //然后扔掉旧的字符串。这样,绝大部分字符串都是临时对象,不但浪费内存,还会影响GC效率。
    public String serialize(TreeNode root) {
        if(root == null) return "null";
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            // 1. 勿忘"null,"逗号  2. continue的作用:避免null上加null
            if(node == null) {
                sb.append("null,");
                continue;
                }
            sb.append(node.val + ",");
            queue.add(node.left);
            queue.add(node.right);
        }
        // 一定要toString();因为return的type是string
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "null") return null;
        String[] str = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        queue.add(root);
        for(int i = 1;i < str.length; i++){
            /*
                1
               / \
              2   3
                 / \
                4   5
            当node 2没有child时,会被从queue中拿出然后 i += 1; 进行下一个node
                */
            TreeNode parent = queue.poll();
            if(!"null".equals(str[i])){
                TreeNode left = new TreeNode(Integer.parseInt(str[i]));
                parent.left = left;
                queue.add(left);
            }
            i += 1;
            if(!"null".equals(str[i])){
                TreeNode right = new TreeNode(Integer.parseInt(str[i]));
                parent.right = right;
                queue.add(right);
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

剑指offer 54 二叉搜索书的第k大节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int k;
    private int ans;
    public int kthLargest(TreeNode root, int k) {
        if(root == null) return 0;
        this.k = k;
        traversal(root);
        return ans;
    }
    // 右 根 左
    public void traversal(TreeNode root){
        if(root == null) return;
        traversal(root.right);
        
        if(--this.k == 0)  this.ans = root.val;
        traversal(root.left);
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容