南阳网站推广优化公司,如何自学编程,wordpress媒体库源码,佛山企业网站建设多少钱以下思路来自于: 代码随想录 (programmercarl.com)
LeetCode T110 平衡二叉树
题目链接:110. 平衡二叉树 - 力扣#xff08;LeetCode#xff09; 题目思路 前面我们说过了,求二叉树的深度我们应该使用前序遍历,求二叉树的高度我们应该使用后序遍历,因为后序遍历可以将子树的… 以下思路来自于: 代码随想录 (programmercarl.com)
LeetCode T110 平衡二叉树
题目链接:110. 平衡二叉树 - 力扣LeetCode 题目思路 前面我们说过了,求二叉树的深度我们应该使用前序遍历,求二叉树的高度我们应该使用后序遍历,因为后序遍历可以将子树的高度返回给父节点,这样层层递归就能得到答案,而深度是从根节点下去一直到空节点为止,这里清楚了这个逻辑,我们就可以来做这道题了,我们知道一个平衡二叉树的高度差是小于等于1的,而不是平衡二叉树的话只需任意子树的高度大于即可,这里我们仍然使用递归完成 1.确定参数和返回值 求高度,返回值是int 只需传入一个节点即可 int getHeight(TreeNode node) 2.确定终止条件 这里我们遇到空节点处即可返回 if(node null){return 0;} 3.确定一次递归逻辑 我们默认如果不是平衡二叉树就返回-1即可,我们按照左右根进行遍历 注:每次获取完左右子树记得判断一次 int leftHeight getHeight(node.left);if(leftHeight -1){return -1;}int rightHeight getHeight(node.right);if(rightHeight -1){return -1;}if(Math.abs(rightHeight-leftHeight)1){return -1;}else{return 1Math.max(leftHeight,rightHeight);} 题目代码
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;}int getHeight(TreeNode node){if(node null){return 0;}int leftHeight getHeight(node.left);if(leftHeight -1){return -1;}int rightHeight getHeight(node.right);if(rightHeight -1){return -1;}if(Math.abs(rightHeight-leftHeight)1){return -1;}else{return 1Math.max(leftHeight,rightHeight);}}
}
LeetCode T257 二叉树的所有路径
题目链接:257. 二叉树的所有路径 - 力扣LeetCode 题目思路 这里我们注意,使用到了回溯算法,其实递归和回溯是相辅相成的,就以上题的示例1为例,我们再记录了125这一条路线的时候还得回去记录13这一条路径,这就用到了回溯.这里千万不要把递归和回溯拆开,因为有一个递归就有一个回溯. 题目代码
class Solution {public ListString binaryTreePaths(TreeNode root) {ListString res new ArrayList();if(root null){return null;}ListInteger path new ArrayList();travsal(root,path,res);return res;}void travsal(TreeNode node,ListInteger path,ListString res){//前序path.add(node.val);if(node.left null node.right null){StringBuilder sb new StringBuilder();for(int i 0;ipath.size()-1;i){sb.append(path.get(i)).append(-);}sb.append(path.get(path.size()-1));res.add(sb.toString());}if(node.left ! null){//一次递归一次回溯travsal(node.left,path,res);path.remove(path.size()-1);}if(node.right ! null){travsal(node.right,path,res);path.remove(path.size()-1);}}
} LeetCode T404 左叶子之和 题目链接:力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目思路 这里我们注意之前我们只能判断叶子结点,而不能知道左叶子节点,这里我们就可以用过叶子结点的上一个节点知道是否为左叶子节点,这里我们仍然使用递归实现,这里就不需要额外创建新函数(仍然使用后序遍历) 1.函数返回值和参数 public int sumOfLeftLeaves(TreeNode root) 2.终止条件 无论是遇到空节点或者叶子节点都返回0,因为我们不知道该叶子结点是否为我们需要收集的节点 if(root null){return 0;}if(root.left null root.right null){return 0;} 3.单层递归 //后序int leftNum sumOfLeftLeaves(root.left);int rightNum sumOfLeftLeaves(root.right);int sum 0;//中间处理过程if(root.left ! null root.left.left null root.left.right null){sum root.left.val;}sum sum leftNum rightNum;return sum; 题目代码
class Solution {public int sumOfLeftLeaves(TreeNode root) {if(root null){return 0;}if(root.left null root.right null){return 0;}//后序int leftNum sumOfLeftLeaves(root.left);int rightNum sumOfLeftLeaves(root.right);int sum 0;if(root.left ! null root.left.left null root.left.right null){sum root.left.val;}sum sumleftNumrightNum;return sum;}}
