【基础算法精讲 10】如何灵活运用递归？
100. 相同的树
给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){//边界值：当前节点为空时，则返回falseif(p==null||q==null){returnp==q;//都为null，则返回true}//相同的树：当前节点的值相等，且左子树相等，右子树相等。returnp.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}101. 对称二叉树
给你一个二叉树的根节点root， 检查它是否轴对称。
思路：在相同的树这段代码上改，判断左子树的左孩子是否等于右子树的右孩子，左子树的右孩子是否等于右子树的左孩子 代码：classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){if(p==null||q==null){returnp==q;}returnp.val==q.val&&isSameTree(p.left,q.right)&&isSameTree(p.right,q.left);}publicbooleanisSymmetric(TreeNoderoot){//可以在相同的树代码逻辑上改//看左子树的左孩子是否等于右子树的右孩子，左子树的右孩子是否等于左子树的右孩子returnisSameTree(root.left,root.right);}}110. 平衡二叉树
给定一个二叉树，判断它是否是平衡二叉树
思路： 用-1表示该树不是平衡二叉树，如果该树中某一个节点不是平衡节点，就立马返回-1，一直返回到调用入口，表示该树为非平衡二叉树。 代码：classSolution{//获得子树高度publicintgetDepth(TreeNodenode){if(node==null){return0;}//获取左子树高度intleft_height=getDepth(node.left);if(left_height==-1){return-1;}//获取右子树高度intright_height=getDepth(node.right);if(right_height==-1||Math.abs(left_height-right_height)>1){return-1;}returnMath.max(left_height,right_height)+1;}publicbooleanisBalanced(TreeNoderoot){//用-1记录该树为非平衡二叉树returngetDepth(root)!=-1;}}199. 二叉树的右视图
给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
思路：1、用一个全局数组ans,初始值为空。2、先遍历右子树，比较当前树的深度是否大于数组长度，若大于，则表示该节点是被第一次看见，需要记录到答案数组中。3、必须先遍历右子树，再遍历左子树 代码：classSolution{List<Integer>ans=newArrayList<>();publicvoiddepth(TreeNodenode,intdepth){if(node==null){return;}depth+=1;if(depth>ans.size()){ans.add(node.val);}//必须先遍历右子树depth(node.right,depth);depth(node.left,depth);}publicList<Integer>rightSideView(TreeNoderoot){//先遍历右子树//若答案的长度小于当前树的深度时，证明该节点是第一个能看到的结点，要把该节点记录到答案中。depth(root,0);returnans;}}