M
2020-12-28 22:43:14 66 庶卒 参与编辑 版本: 1 引用率 28.70%
# 树

## 1 二叉树的最大深度95.26%      
```java
public class Solution {100.00%      
    public int maxDepth (TreeNode root) {
        // write code here100.00%      
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1 + Math.max(left, right);
    }
}
```

## 2 判断是否是平衡二叉树100.00%      
输入一棵二叉树,判断该二叉树是否是平衡二叉树。90.87%      

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

平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。61.42%      
```java
public class Solution {100.00%      
    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;100.00%      
        } else {100.00%      
            return 1 + (left > right ? left : right);
        }
    }
}
```

## 3 合并二叉树85.13%      
```java
public class Solution {100.00%      
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {87.29%      
        // 以t1树为主
        t1.val = t1.val + t2.val;69.44%      
        // 如果两个树的左子树都存在,进行合并
        if (t1.left != null && t2.left != null) mergeTrees(t1.left, t2.left);85.77%      
        // 如果t1的左子树不存在,吧t2的左子树赋给t1
        else if (t1.left == null && t2.left != null) t1.left = t2.left;87.29%      
        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个节点83.33%      
```java
public class Solution {100.00%      
    // 二叉搜索树 左子树比根小,右子树比根大
    // 中序遍历 先左 在中 后右
    TreeNode KthNode(TreeNode pRoot, int k) {100.00%      
        if (pRoot == null || k <= 0) return null;
        // 用栈存放所有根的数据
        Stack rootStack = new Stack<>();77.46%      
        TreeNode cur = pRoot;
        while (!rootStack.isEmpty() || cur != null) {
            if (cur != null) {
                // 不为空 吧根节点压入栈中
                rootStack.push(cur);
                // 中序遍历 开始处理左子树 
                cur = cur.left;
            } else {100.00%      
                // 当前节点为空,取出当前节点的根节点61.24%      
                cur = rootStack.pop();
                // 取出,说明已经到最小的值了,开始判断是否是倒数第k个值
                if (--k == 0) return cur;
                // 不是倒数第k个值,取右子树
                cur = cur.right;
            }
        }
        return null;
    }
}
```

## 5 二叉树中是否存在节点和为指定值得路径63.25%      
给定一个二叉树和一个值\ sum sum,判断是否有从根节点到叶子节点的节点值之和等于\ sum sum 的路径,
```java
public class Solution {100.00%      
    public boolean hasPathSum (TreeNode root, int sum) {60.30%      
        // 先序遍历
        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树拓扑结构
```java
public class Solution {100.00%      
    public boolean isContains (TreeNode root1, TreeNode root2) {90.91%      
        // 中序遍历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 二叉树的镜像93.64%      
```java
public class Solution {100.00%      
    public void Mirror(TreeNode root) {100.00%      
        if (root == null) return;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}
```

## 8 判断二叉树是否对称85.71%      
给定一棵二叉树,判断琪是否是自身的镜像(即:是否对称)65.47%      
备注:
希望你可以用递归和迭代两种方法解决这个问题
```java
public class Solution {100.00%      
    public boolean isSymmetric (TreeNode root) {
        // write code here100.00%      
        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) {77.46%      
        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) {60.30%      
        Stack left = new Stack<>();77.46%      
        Stack 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 将升序数组转化为平衡二叉树68.38%      
```java
public class Solution {100.00%      
    public TreeNode sortedArrayToBST (int[] num) {
        // write code here100.00%      
        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]);71.43%      
        root.left = sortedArrayToBST(num, left, mid - 1);
        root.right = sortedArrayToBST(num, mid + 1, right);
        return root;100.00%      
    }
}
```

## 10 重建二叉树92.58%      
```java
public class Solution {100.00%      
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) return null;
        // 根节点为先序的第一个值
        TreeNode root = new TreeNode(pre[0]);77.15%      
        for (int i = 0; i < in.length; i++) {
            // 在中序中查找根节点62.55%      
            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;100.00%      
            }
        }
        return root;100.00%