Leetcode刷题——543. 二叉树的直径、617. 合并二叉树（递归解决）

递归

解决这两道题我想先理一理递归的思路，解决递归问题要有三个要素：

1. 方法参数和返回值

• 方法参数：方法参数有两种情况
  • 如果和前面有关系，那就得设置为全局变量
    例如刷题中的538题，就会出问题，导致传过来的值不是最新的，下面的543题也是一样.
  • 如果和前面没关系，也就是说是一个只会在当前层作用，即局部的，就通过方法体传递过来
• 返回值
  当需要用到返回值的时候，设置返回值，下面两道题都会需要，
  而上面提到的刷题中的538题，已经使用sum记录了我需要的值，不需要返回值操作。另外，一般判断的都带返回值，有false直接返回了。

2. 终止条件
   是自己需要明确的地方，到什么时候停止什么时候结束。
3. 函数体
   对于节点和数据的操作

下面的题目，我会通过以上三步进行分析

543. 二叉树的直径

543. 二叉树的直径
这道题翻译一下，找出每个节点的左右子树的高度之和中最大的。
为什么抢到每个节点，因为我一开始是用层次遍历做的，以为必然是从跟节点出发的，这个想法是错的，举个例子，根的右子树的高度是1，左子树是两个一样高的子树，高度都为10。
代码：

	//写在外面是因为这是全局变量，找到全局最大的。
	int ans;
    public  int diameterOfBinaryTree(TreeNode root) {
    
        depth(root);
        return ans;
    }
	//设置返回值是因为求高度需要用到
    private  int depth(TreeNode root){
    
        //结束条件
        if(root == null){
    
            return 0;
        }
        //方法体
        // 递归求当前节点左右子树的高度
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        ans = Math.max(ans,leftDepth+rightDepth);
        //返回当前子树的高度
        return Math.max(leftDepth,rightDepth)+1;
    }

617. 合并二叉树

617. 合并二叉树
题目很好理解，思路，有新的就接上去

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    
        return build(root1, root2);
    }
    //先序遍历。
    //设置返回值是因为建树需要用到
    public static TreeNode build(TreeNode root1, TreeNode root2){
    
		//终止条件
		//叶子结点，直接返回
        if(root1==null &&  root2==null) return null;
        //还有羊毛薅，可冲
        if(root1!=null && root2==null) return root1;
        if(root1==null && root2!=null) return root2;
        //左右子树的重叠部分，需要叠加，
        TreeNode node = new TreeNode(root1.val + root2.val);
        //建树，这里可见需要用的返回值。
        node.left=build(root1.left, root2.left);
        node.right=build(root1.right,root2.right);
        return node;
    }