Binary Tree的题目总结(一)

与数组和链表相比，树的题目比它们要难一些，我们往往通过递归来处理树的题目，下面是对leetcode有关树操作的几道题目，包括找出树的所有路径，计算完全二叉树节点个数，二叉搜索树的最近公共祖先，普通二叉树的最近公共祖先。

1，Binary Tree Paths
给定一个二叉树，输出所有根节点到叶子节点的路径。

用深度优先遍历(DFS)，依次保留搜索过的节点。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new LinkedList<String>();
        if(root == null) return list;
        String str = String.valueOf(root.val);
        DFS(root, str, list);
        return list;
    }
    private void DFS(TreeNode root, String str, List<String> list) {
        if(root.left == null && root.right == null) 
            list.add(str);
        if(root.left != null) 
            DFS(root.left, str + "->" + root.left.val, list);
        if(root.right != null)
            DFS(root.right, str + "->" + root.right.val, list);
        
    }
}

2，Count Complete Tree Nodes
给定一个完全二叉树，计算树中节点的个数。

既然是完全二叉树，我们要好好利用它特有的性质，完全二叉树只有最后一层不满，并且节点是从左到右排列的。一个n层满二叉树的节点个数为2^n - 1，因此我们可以利用这些性质来处理这道题。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int leftnode = -1;
        int rightnode = -1;
        return countNodes(root, leftnode, rightnode);
    }
    
    private int countNodes(TreeNode root, int leftnode, int rightnode){
        if(leftnode == -1) {
            TreeNode cur = root;
            while(cur != null) {
                leftnode ++;
                cur = cur.left;
            }
        }
        
        if(rightnode == -1) {
            TreeNode cur = root;
            while(cur != null) {
                rightnode ++;
                cur = cur.right;
            }
        }
        
        if(leftnode == rightnode) return (1 << leftnode) - 1;
        return 1 + countNodes(root.left, leftnode -1, -1) + countNodes(root.right, -1, rightnode -1);
    }
}

3，Lowest Common Ancestor of a Binary Search Tree
给定一个二叉搜索树，查找两个节点的最近公共祖先。

不清楚公共祖先定义的查阅网上资料。二叉搜索树的性质是左子树的值都小于根节点值，右子树的值都大于根节点的值，我们可以通过值的比较来判断要查找的两个节点的位置，从而找到公共祖先。代码如下：

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

4，Lowest Common Ancestor of a Binary Tree
给定一个二叉树，找到两个节点的公共祖先。

与第三题不同，它是一个普通的二叉树，我们不能通过值来判断两个节点的位置，我们用深度优先搜索，通过返回值来判断两个节点的位置，代码如下：

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