Tag: 递归

这题比较有意思, 拿来分享一下: 在二叉树中, 根节点在深度0处, 并且每个深度k节点的子节点在深度k + 1处. 如果二元树的两个节点具有相同的深度但具有不同的父节点, 则它们是堂/表兄弟. 我们给出了具有唯一值的二叉树的根, 以及树中两个不同节点的值x和y. 当且仅当对应于值x和y的节点是同类时, 才返回true. 例如: 1 2 3 2和3的父母是同一个, 所以不是表兄弟(妹) 1 2 3 4 5 4和5是, 因为来自不同的父母, 并且所以树的高度是一样的. 深度优先+递归 二叉树(或者图)的一些算法大多数都可以用深度优先DFS来实现, …

题意: 给定一个二分查找树 BST, Binary Search Tree, 查找指定的元素, 返回该节点开始的子树. 如果没找到就返回NULL. 给定 4 / \ 2 7 / \ 1 3 如果我们要查找 2, 则返回子树: 2 / \ 1 3 二叉树在C/C++中的定义 二叉树可以用结构体来定义, …

题意: 合并两个二叉树, 没有说不可以改变原来的二叉树. 合并的时候把结点求合. C/C++ 中二叉树的定义 在C或者C++中, 二叉树的定义可以很方便的用结构体来表征. 其中左右子树都是递归定义. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) …

题意: 给定一个字符串, 输出所有字符大小写都可以组成的字符串. 如: “ab1” 能成生 DFS 深度优先 – 递归 我们可以从字符串的开头递归的把当前字符给添加到最终的字符串中, 当当前字符是字母的时候, 就有两种可能了. 当到达字符串尾部的时候我们把当前字符串添加到结果数组中即可. class Solution { public: vector<string> letterCasePermutation(string S) { search("", S, 0, S.length() - 1); return …

题意: 找出N叉树的最大深度. 上面这颗树, 深度为3. N叉树的C++定义 // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val, vector<Node*> _children) { val = _val; children …

题意: 找出所有左子树上的叶节点的值之和. 3 / \ 9 20 / \ 15 7 比如上面 9 和15是左子树上的子节点, 那么求和得 24. 一般来说, 遍历树有两种方式: 深度优先DFS和广度优先BFS. 解这题的关键就在需要知道叶子节点是从左边来的还是从右边来的. C++ 定义二叉树 struct TreeNode { int val; TreeNode *left; …

今天我们要来讲一讲递归. 递归就是函数自己调用自己, 我们可以定义一个过程, 然后这只海龟不停的画, 结束的时候再调用自身再继续画. 再次调用的时候参数变化了, 至到参数满足一定的条件则停止. 比如 下面定义的这个过程可以用来画一个实现的正方形. TO FK :B IF :B>15 ; 如果边长大于15就停止 REPEAT 4 ; Draw a square with side B 画一个长度为B的正方形 FK :B+1 ; …