力扣刷题——树

解题思路

利用分治的思想，进行递归，先数据相加，再计算左右孩字，左右孩子又重复以上步骤。。。。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null)    return t2;
        else if(t2==null)   return t1;
        else{
            t1.val = t1.val + t2.val;
            t1.left = mergeTrees(t1.left,t2.left);
            t1.right = mergeTrees(t1.right,t2.right);
            return t1;
        }
    }
}

           

递归解决法：

/**
 * 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) {
           return root==null ? 0 : Math.max(maxDepth(root.left),
           maxDepth(root.right))+1;
    }
}
           

非递归解决法

LinkedList中add和offer的区别

 offer属于 offer in interface Deque，add 属于 add in interface Collection。 当队列为空时候，使用add方法会报错，而offer方法会返回false。

 作为List使用时,一般采用add / get方法来 压入/获取对象。

 作为Queue使用时,才会采用 offer/poll/take等方法作为链表对象时,offer等方法相对来说没有什么意义这些方法是用于支持队列应用的。

BFS

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int level = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return level;
    }
}
           

DFS

class Solution {
    int maxLevel = 0;

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, 1);
        return maxLevel;
    }

    public void dfs(TreeNode root, int level) {
        if (root == null)
            return;
        if (level > maxLevel) maxLevel = level;
        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }
}