哪些php网站,网站建设中 尽情期待,如果做微商需不需要开个网站。,读书分享会ppt模板免费下载前言#xff1a; 本章节更深入学习递归
计算布尔二叉树的值 思路#xff1a; 1.函数头设计#xff1a;dfs#xff08;root#xff09; 2.函数体#xff1a;需要一个接收left 和 right 的值 并且根据root的值进行比较 3.递归出口#xff1a;很明显 当为叶子节点的时候…前言 本章节更深入学习递归
计算布尔二叉树的值 思路 1.函数头设计dfsroot 2.函数体需要一个接收left 和 right 的值 并且根据root的值进行比较 3.递归出口很明显 当为叶子节点的时候 向上返回你叶子节点的值 并且与当前root的值进行比较 public boolean evaluateTree(TreeNode root) {if(root.left null root.right null) {return root.val 0;}boolean left evaluateTree(root.left);boolean right evaluateTree(root.right);return root.val 2 ? left || right : left right;} 求根节点到叶节点数字之和 从根节点开始遍历每个节点如果遇到叶子节点则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点则计算其子节点对应的数字然后对子节点递归遍历。 int ret 0;public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int preSum) {preSum preSum * 10 root.val;if (root.left null root.right null) {return ret preSum;}if (root.left ! null) {dfs(root.left, preSum);}if (root.right ! null) {dfs(root.right, preSum);}return ret;} 二叉树剪枝 思路 叶子节点为0 直接让它指向空 后序遍历思想 1.遍历完左子树 再遍历右子树 2. 如果遇到叶子节点 则判断当前节点是否为0 3.如果为0 则直接返回null 否则不需要剪枝 直接返回原来值 public TreeNode pruneTree(TreeNode root) {if (root null) {return null;}root.left pruneTree(root.left);root.right pruneTree(root.right);if (root.left null root.right null root.val 0) {return null;} else {return root;}} 验证二叉搜索树 思路二叉搜索树 中序遍历是一个有序数组 利用这一特性 先定义一个最小数字prev 当遍历完左子树回退时候 比较是否prev跟当前回退的数字大小 如果比prev大 则让prev当前节点的值 否则 就不是二叉搜索树 long prev Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root null) {return true;}if (!isValidBST(root.left) || root.val prev) {return false;}prev root.val;return isValidBST(root.right);} 二叉搜索树中第 K 小的元素 思路 要求二叉搜索树第k大的数字 定义俩个全局变量 ret记录最终结果 count记录当前k 依次遍历到左子树 当为空的时候 就该回退了 并且 count-1 当count为0的时候 就是目标值了 int ret;int count ;public int kthSmallest(TreeNode root, int k) {count k;dfs(root);return ret;}public void dfs(TreeNode root) {if(root null) {return ;}dfs(root.left);count--;if(count 0) {ret root.val;return ;}dfs(root.right);}
