树

1 二叉树的最大深度

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

2 判断是否是平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root) != -1;
    }
    
    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        if (left == -1) return -1;
        int right = depth(root.right);
        if (right == -1) return -1;
        if (left - right < -1 || left - right > 1) {
            return -1;
        } else {
            return 1 + (left > right ? left : right);
        }
    }
}

3 合并二叉树

public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // 以t1树为主
        t1.val = t1.val + t2.val;
        // 如果两个树的左子树都存在，进行合并
        if (t1.left != null && t2.left != null) mergeTrees(t1.left, t2.left);
        // 如果t1的左子树不存在，吧t2的左子树赋给t1
        else if (t1.left == null && t2.left != null) t1.left = t2.left;
        if (t1.right != null && t2.right != null) mergeTrees(t1.right, t2.right);
        else if (t1.right == null && t2.right != null) t1.right = t2.right;
        return t1;
    }
}

4 二叉搜索树的第k个节点

public class Solution {
    // 二叉搜索树 左子树比根小，右子树比根大
    // 中序遍历 先左 在中 后右
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k <= 0) return null;
        // 用栈存放所有根的数据
        Stack<TreeNode> rootStack = new Stack<>();
        TreeNode cur = pRoot;
        while (!rootStack.isEmpty() || cur != null) {
            if (cur != null) {
                // 不为空 吧根节点压入栈中
                rootStack.push(cur);
                // 中序遍历 开始处理左子树 
                cur = cur.left;
            } else {
                // 当前节点为空，取出当前节点的根节点
                cur = rootStack.pop();
                // 取出，说明已经到最小的值了，开始判断是否是倒数第k个值
                if (--k == 0) return cur;
                // 不是倒数第k个值，取右子树
                cur = cur.right;
            }
        }
        return null;
    }
}

5 二叉树中是否存在节点和为指定值得路径

给定一个二叉树和一个值\ sum sum，判断是否有从根节点到叶子节点的节点值之和等于\ sum sum 的路径，

public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        // 先序遍历
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            if (sum - root.val == 0) return true;
            else return false;
        }
        boolean left = hasPathSum(root.left, sum - root.val);
        boolean right = hasPathSum(root.right, sum - root.val);
        return left || right;
    }
}

6 判断t1树中是否包含t2树拓扑结构

public class Solution {
    public boolean isContains (TreeNode root1, TreeNode root2) {
        // 中序遍历root1和root2，获得字符串，判断是否包含即可
        StringBuilder b1 = new StringBuilder();
        StringBuilder b2 = new StringBuilder();
        preOrder(root1, b1);
        preOrder(root2, b2);
        return b1.toString().contains(b2.toString());
    }
    
    private static void preOrder(TreeNode root, StringBuilder b) {
        if (root == null) return;
        preOrder(root.left, b);
        b.append(root.val);
        preOrder(root.right, b);
    }
}

7 二叉树的镜像

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

8 判断二叉树是否对称

给定一棵二叉树，判断琪是否是自身的镜像（即：是否对称）
备注：
希望你可以用递归和迭代两种方法解决这个问题

public class Solution {
    public boolean isSymmetric (TreeNode root) {
        // write code here
        if (root == null) return true;
        if (root.left == null && root.right == null) return true;
        boolean one = isSymmetric(root.left, root.right);
        boolean two = isSymmetric2(root);
        return one && two;
    }
    
    // 递归的方式
    private boolean isSymmetric (TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
    
    // 迭代的方式
    private boolean isSymmetric2 (TreeNode root) {
        Stack<TreeNode> left = new Stack<>();
        Stack<TreeNode> right = new Stack<>();
        left.push(root.left);
        right.push(root.right);
        while (!left.isEmpty() && !right.isEmpty()) {
            TreeNode l = left.pop();
            TreeNode r = right.pop();
            if (l == null && r == null) continue;
            if (l == null || r == null) return false;
            if (l.val != r.val) return false;
            left.push(l.left);
            left.push(l.right);
            right.push(r.right);
            right.push(r.left);
        }
        if (left.isEmpty() && right.isEmpty()) return true;
        return false;
    }
}

9 将升序数组转化为平衡二叉树

public class Solution {
    public TreeNode sortedArrayToBST (int[] num) {
        // write code here
        return sortedArrayToBST(num, 0, num.length - 1);
    }
    private TreeNode sortedArrayToBST(int[] num, int left, int right) {
        if (left > right) return null;
        // 为啥要加一呢？因为分为三个部分，左子树、根、右子树
        int mid = (left + right + 1) >> 1;
        TreeNode root = new TreeNode(num[mid]);
        root.left = sortedArrayToBST(num, left, mid - 1);
        root.right = sortedArrayToBST(num, mid + 1, right);
        return root;
    }
}

10 重建二叉树

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) return null;
        // 根节点为先序的第一个值
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            // 在中序中查找根节点
            if (in[i] == pre[0]) {
                // 根节点左边的中序即左子树的中序，右边中序即右子树的中序
                // 注意排除根节点
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }
}