基础算法题-树相关

1. 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

可用递归方式解决。首先利用前序遍历集合的根节点，将中序遍历和前序遍历的结果各分割成两部分，为左右子树的前序遍历集合和中序遍历集合。
代码如下：

TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    if (in.length == 0 | pre.length == 0) return null;
    TreeNode treeNode = new TreeNode(pre[0]);
    int count = 0;
    for (int i = 0; i < in.length; i++) {
        if (in[i] == pre[0]) break;
        count++;
    }
    int[] pre2 = new int[count];
    int[] in2 = new int[count];
    int[] pre3 = new int[in.length - count - 1];
    int[] in3 = new int[in.length - count - 1];
    for (int j = 0; j < count; j++) {
        pre2[j] = pre[1 + j];
        in2[j] = in[j];
    }
    for (int k = 0; k < in.length - count - 1; k++) {
        pre3[k] = pre[count + 1 + k];
        in3[k] = in[count + 1 + k];
    }
    treeNode.left = reConstructBinaryTree(pre2, in2);
    treeNode.right = reConstructBinaryTree(pre3, in3);
    return treeNode;
}

2. 输入两棵二叉树A，B，判断B是不是A的子结构。

递归实现。分别判断B是A的子结构，B是否是A左右子树的子结构即可。
代码如下：

boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if (root2 == null | root1 == null) return false;
    return IsSimilarity(root1, root2) | HasSubtree(root1.right, root2) | HasSubtree(root1.left, root2);
}

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

3. 操作给定的二叉树，将其变换为源二叉树的镜像。

递归实现。先镜像根节点的左右子树，再将左右子树互换。两者操作顺序不影响结果。
代码如下：

void Mirror(TreeNode root) {
    if (root == null) return;
    Mirror(root.left);
    Mirror(root.right);

    TreeNode node = root.left;
    root.left = root.right;
    root.right = node;
}

4. 从上往下打印出二叉树的每个节点，同层节点从左至右打印。

利用队列即可。代码如下：

ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    if (root == null) return null;
    ArrayList<Integer> array = new ArrayList<Integer>();
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode pointer = queue.poll();
        array.add(pointer.val);
        if (pointer.left != null)
            queue.add(pointer.left);
        if (pointer.right != null)
            queue.add(pointer.right);
    }
    return array;
}

5. 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

递归解决。先找数组尾部的头结点，通过头结点找出数组左右子树的分割点。分割点右边的数应该都比头结点值大。再将左右子树递归判断即可。
代码如下：

boolean VerifySquenceOfBST(int[] sequence) {
    if (sequence.length < 1) return false;
    int index = sequence.length - 1;
    return VerifySquence(sequence, 0, index);
}

boolean VerifySquence(int[] array, int begin, int last) {
    int length = last - begin + 1;
    if (length < 3) return true;
    if (length > 2) {
        int root = array[last];
        int mid = 0;
        boolean flag = false;
        for (int i = begin; i <= last; i++) {
            if (array[i] > root) {
                mid = i - 1;
                flag = true;
            }
            if (flag && array[i] < root) {
                return false;
            }
        }
        return VerifySquence(array, begin, mid) && VerifySquence(array, mid + 1, last - 1);
    }
    return false;
}

6. 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

通过一个List记录路径，当遇到叶子结点时，路径值和刚好等于目标值。则将这条路保存，然后移除List中的叶子路径，再探测其他路径。若大于目标值，则直接返回即可。可递归实现。
代码如下：

ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> array = new ArrayList<Integer>();

ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    if (root == null) return path;
    if (root.val > target) return path;
    if (root.left == null && root.right == null && target == root.val) {
        array.add(root.val);
        path.add((ArrayList<Integer>) array.clone());
        array.remove((Integer) root.val);
    }
    if (root != null) {
        array.add(root.val);
        FindPath(root.left, target - root.val);
        FindPath(root.right, target - root.val);
        array.remove((Integer) root.val);
    }
    return path;
}

7. 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

首先将左右子树递归改成双向链表，然后配置左右子树与根节点的关系。将根节点放置在左子树的最右边结点的后面。将右子树的最左边的结点的left指向根节点。然后一道双向链表的最左端结点，返回即可。
代码如下：

TreeNode Convert(TreeNode pRootOfTree) {
    if (pRootOfTree == null) return null;
    if (pRootOfTree != null) {
        TreeNode node = Convert(pRootOfTree.left);
        while (node != null && node.right != null) {
            node = node.right;
        }
        if (node != null) {//要注意边界 为null的情况
            node.right = pRootOfTree;
        }
        pRootOfTree.left = node;
        TreeNode node1 = Convert(pRootOfTree.right);
        pRootOfTree.right = node1;
        if (node1 != null) {
            node1.left = pRootOfTree;
        }
    }
    while (pRootOfTree.left != null) {
        pRootOfTree = pRootOfTree.left;
    }
    return pRootOfTree;
}

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

首先通过获取树的深度，然后判断左右子树深度之差是否符合平衡。递归解决。
代码如下：

boolean IsBalanced_Solution(TreeNode root) {
    if (root == null) return true;
    boolean left = IsBalanced_Solution(root.left);
    boolean right = IsBalanced_Solution(root.right);
    if (left && right) {
        int depthLeft = TreeDepth(root.left);
        int depthRight = TreeDepth(root.right);
        if (Math.abs(depthLeft - depthRight) < 2)
            return true;
        else
            return false;
    }
    return left && right;
}

int TreeDepth(TreeNode root) {
    if (root == null) return 0;
    int depthLeft = TreeDepth(root.left);
    int depthRight = TreeDepth(root.right);
    return depthLeft > depthRight ? depthLeft + 1 : depthRight + 1;
}

9. 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

递归实现，分别判断左右子树的左右子树是否对应相等。
代码如下：

boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null) 
         return true;
    return isSymm(pRoot.left, pRoot.right);
}

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

10. 请实现两个函数，分别用来序列化和反序列化二叉树。

在每个结点的值后添加’,’,null结点用’#’表示，利用中序遍历的方式序列化。利用index记录复原到哪一位字符。
代码如下：

int index = -1;

String Serialize(TreeNode root) {
    if (root == null) return "#,";
    StringBuilder str = new StringBuilder();
    str.append(root.val + ",");
    str.append(Serialize(root.left));
    str.append(Serialize(root.right));
    return str.toString();
}

TreeNode Deserialize(String str) {
    index++;
    if (index >= str.length())
        return null;
    String[] parts = str.split(",");
    TreeNode root = null;
    if (!parts[index].equals("#")) {
        root = new TreeNode(Integer.parseInt(parts[index]));
        root.left = Deserialize(str);
        root.right = Deserialize(str);
    }
    return root;
}

11. 给定一颗二叉搜索树，请找出其中的第k大的结点。

先统计左子树的数量，若大于K则k结点肯定在左子树中，若小于K则第k个结点可能在根节点或者右子树中。可递归调用。
代码如下：

TreeNode KthNode(TreeNode pRoot, int k) {
    if (pRoot == null) return null;
    int count;
    TreeNode result = pRoot;
    count = getNumOfNodes(pRoot.left);
    if (count >= k)
        return KthNode(pRoot.left, k);
    else if (count + 1 < k)
        return KthNode(pRoot.right, k - count - 1);
    else
        return pRoot;
}

int getNumOfNodes(TreeNode pRoot) {
    if (pRoot == null) return 0;
    int count = 1;
    count = count + getNumOfNodes(pRoot.left) + getNumOfNodes(pRoot.right);
    return count;
}