第10章二叉树 - 二叉树 - 《数据结构与算法》

LeetCode

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

思路：
① 拷贝一棵二叉树，再反转，将反转以后的二叉树和自己比较，看看是否相等。
② 设置一个辅助函数，递归去判断两棵子树是否镜面对称。
③ 还可以使用辅助数据结构“双端队列”完成。使用队列，并且是双端队列（链表实现）这个辅助数据结构。

/**
 * 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 isSym(root.left, root.right);
    }
    private boolean isSym(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if ( (left == null && right != null) || (left != null && right == null) || left.val != right.val) return false;
        return isSym(left.left, right.right) && isSym(left.right, right.left);
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(root.left);
        q2.offer(root.right);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();
            if (node1 == null && node2 == null) continue;
            if((node1 != null && node2 == null) || (node1 == null && node2 != null)) return false;
            if (node1.val != node2.val) return false;
            q1.offer(node1.left);
            q1.offer(node1.right);
            q2.offer(node2.right);
            q2.offer(node2.left);
        }
        return true;
    }
}

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：

一个二叉树每个结点的左右两个子树的高度差的绝对值不超过1。

思路：
对于每一个结点，我们通过checkDepth方法递归获得左右子树的深度。如果子树是平衡的，则返回真实的深度，若不平衡，直接返回-1。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(checkDepth(root) == -1) return false;
        else return true;
    }
    public int checkDepth(TreeNode root) {
        if(root == null) return 0;
        int left = checkDepth(root.left);
        if(left == -1) return -1;
        int right = checkDepth(root.right);
        if(right == -1) return -1;
        int dif = Math.abs(left - right);
        if(dif > 1) return -1;
        else return 1 + Math.max(left, right);
    }
}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根结点到最远叶子结点的最长路径上的结点数。
说明: 叶子结点是指没有子结点的结点。

思路：
使用递归的方法，考虑清楚递归终止条件，解答是非常简单且清楚的。其实本质上是“后序遍历”，从叶子结点开始计算深度。从底向上。写法其实上是二叉树的后序遍历（先左右子树，然后再自己）。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根结点到最近叶子结点的最短路径上的结点数量。**

思路：
和最大深度类似，但是左右孩子有一个为空的时候，要分类判断。

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        if(root.left==null){
            return minDepth(root.right)+1;
        }
        if(root.right==null){
            return minDepth(root.left)+1;
        }
        return Math.min(minDepth(root.left),minDepth(root.right))+1;  
    }
}

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int res = 0;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                TreeNode t = q.poll();
                if (t.left == null && t.right == null) return res;
                if (t.left != null) q.offer(t.left);
                if (t.right != null) q.offer(t.right);
            }
        }
        return -1;
    }
}

226. 翻转二叉树

翻转一棵二叉树。

思路：
使用反转，前序遍历、后序遍历、广度优先遍历都可以实现。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root != null){
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            invertTree(root.left);
            invertTree(root.right);
        }
        return root;
    }
}

100. 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且结点具有相同的值，则认为它们是相同的。

思路：
利用递归解决。和对称二叉树类似。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if ( (p != null && q == null) || (p == null && q != null) || (p.val != q.val) ) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

404. 左叶子之和

计算给定二叉树的所有左叶子之和。

思路：
找递归关系是关键。需要判断是不是左叶子结点，如果是则算上该结点的值。非递归写法用BFS（todo）。

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left != null && root.left.right == null && root.left.left == null) {
            return root.left.val + sumOfLeftLeaves(root.right);
        }

        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

练习：

222. 完全二叉树的结点个数

剑指 Offer

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路：
①递归。根据图中数组确定下一步的参数。
LeetCode 重建二叉树.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder,int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        for (int i = 0; i < inorder.length; i++) {
            if (root.val == inorder[i]) {
                root.left = helper(preorder, preStart + 1, i - inStart + preStart, inorder, inStart, i - 1);
                root.right = helper(preorder, i - inStart + preStart + 1, preEnd, inorder, i + 1, inEnd);
                break;
            }
        }
        return root;
    }
}

②递归。map记录节点信息，更快。

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

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            // 根节点在中序遍历中的位置
            dic.put(inorder[i], i);
        }
        po = preorder;

        return recur(0, 0, inorder.length - 1);
    }

    /**
     * @param preRoot 前序遍历中根节点的索引
     * @param inLeft  中序遍历的左边界
     * @param inRight 中序遍历的右边界
     *
     * @return 返回 root，含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点
     */
    private TreeNode recur(int preRoot, int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }

        // 建立当前根节点
        TreeNode root = new TreeNode(po[preRoot]);

        Integer inMid = dic.get(po[preRoot]);
        // 构造左子树
        root.left = recur(preRoot + 1, inLeft, inMid - 1);
        // 构造右子树
        root.right = recur(preRoot + inMid - inLeft + 1, inMid + 1, inRight);

        return root;
    }
}

③非递归。BFS。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int length = preorder.length;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构，即 A中有出现和B相同的结构和节点值。

思路：
递归。当A和B值相等时，通过helper()函数判断他们的子树是否有符合的，有符合的返回true，没有符合的接着判断A和B的值。

/**
 * 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 (B == null || A == null) {
            return false;
        }
        if (A.val == B.val && (helper(A.left, B.left) && helper(A.right, B.right))) {
            return true;
        }
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean helper(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (root1.val == root2.val) {
            return helper(root1.left, root2.left) && helper(root1.right, root2.right);
        } else {
            return false;
        }
    }
}

剑指 Offer 27. 二叉树的镜像

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

思路：
①二叉树。递归。

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

②利用辅助栈。

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. 对称的二叉树

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

思路：
二叉树。助手函数递归实现。

/**
 * 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 helper(root.left, root.right);
    }

    private boolean helper(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right != null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return helper(left.right, right.left) && helper(left.left, right.right);
    }
}

剑指 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 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return rSerialize(root, "");
    }

    private String rSerialize(TreeNode root, String str) {
        if (root == null) {
            str += "#,";
        } else {
            str += String.valueOf(root.val) + ",";
            str = rSerialize(root.left, str);
            str = rSerialize(root.right, str);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] arr = data.split(",");
        List<String> list = new ArrayList<>(Arrays.asList(arr));
        return rDeserialize(list);
    }

    private TreeNode rDeserialize(List<String> list) {
        if (list.get(0).equals("#")) {
            list.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        root.left = rDeserialize(list);
        root.right = rDeserialize(list);

        return root;
    }
}

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

②广度优先搜索（更快）。

public class Codec {
    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;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        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 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

思路：
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.5 MB, 在所有 Java 提交中击败了100.00%的用户

/**
 * 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 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

思路：
对于每一个节点，我们通过checkDepth方法递归获得左右子树的深度。如果子树是平衡的，则返回真实的深度，若不平衡，直接返回-1。
执行用时：1 ms, 在所有 Java 提交中击败了99.91%的用户
内存消耗：39.7 MB, 在所有 Java 提交中击败了100.00%的用户

/**
 * 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 (checkDepth(root) == -1) {
            return false;
        }
        return true;
    }

    private int checkDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = checkDepth(root.left);
        if (left == -1) {
            return -1;
        }
        int right = checkDepth(root.right);
        if (right == -1) {
            return -1;
        }
        int dif = Math.abs(left - right);
        if (dif > 1) {
            return -1;
        } else {
            return 1 + Math.max(left, right);
        }
    }
}

思路2：
获取高度，进行判断。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
            return false;
        } else {
            return isBalanced(root.left) && isBalanced(root.right);
        }
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
}

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：
后序遍历。
执行用时：7 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了100.00%的用户

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }

        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        if (left == null ) {
            return right;
        }
        return left;
    }
}