亚马逊网站域名,网站页面排名优化,广州公司网站制作费用,泊头 网站优化二叉树一般都是和递归有联系的#xff0c;二叉树的遍历包括了前序#xff0c;后序#xff0c;中序#xff0c;大部分题目只要考虑清楚应该用那种遍历顺序#xff0c;然后特殊情况的条件#xff0c;题目就会迎刃而解。
1. 先来说说二叉树的遍历方式
其实二叉树的遍历很简…二叉树一般都是和递归有联系的二叉树的遍历包括了前序后序中序大部分题目只要考虑清楚应该用那种遍历顺序然后特殊情况的条件题目就会迎刃而解。
1. 先来说说二叉树的遍历方式
其实二叉树的遍历很简单无论是前后中序都只需要记住三个步骤
递归的参数和返回值递归终止条件递归单层逻辑
1. 1前序遍历根左右
// 不需要返回值遍历当前树就可以
void preOrder(TreeNode* root) {if(root nullptr) return; // 终止条件// 单层逻辑cout root-val; // 根preOrder(root-left); // 左preOrder(root-right); // 右
}1.2 后序遍历左右根
// 不需要返回值遍历当前树就可以
void postOrder(TreeNode* root) {if(root nullptr) return; // 终止条件// 单层逻辑postOrder(root-left); // 左cout root-val; // 根postOrder(root-right); // 右
}1.3 中序遍历左根右
// 不需要返回值遍历当前树就可以
void postOrder(TreeNode* root) {if(root nullptr) return; // 终止条件// 单层逻辑postOrder(root-left); // 左cout root-val; // 根postOrder(root-right); // 右
}2. 上题目
2.1 对称二叉树 Leetcode
分析什么是对称二叉树左子树右子树就是对称。返回值和参数。因为要比较左右两棵树因此参数(TreeNode* left_tree, TreeNode* right_tree)这里需要比较左右子树判断是否相等因此返回值bool
bool isLeftEqualRight(TreeNode* left_tree, TreeNode* right_tree)终止条件。也是处理特殊情况 if(left_tree nullptr right_tree nullptr) return true;if(left_tree nullptr right_tree ! nullptr) return false;if(left_tree ! nullptr right_tree nullptr) return false;单层逻辑。想象成一个有三个节点左中右的二叉树此时应该如何处理。在这里就要考虑遍历顺序的问题了。是先处理根节点还是后处理根节点。这里明显是先处理根节点。
if(left_tree-val ! right_tree-val) return false;
bool b1 dfs(left_tree-left, right_tree-right);
bool b2 dfs(left_tree-right, right_tree-left);return b1 b2;整体代码
bool isSymmetric(TreeNode* root) {if(root nullptr) return true;return isLeftEqualRight(root-left, root-right);
}bool isLeftEqualRight(TreeNode* left_tree, TreeNode* right_tree) {// 终止条件if(left_tree nullptr right_tree nullptr) return true;if(left_tree nullptr right_tree ! nullptr) return false;if(left_tree ! nullptr right_tree nullptr) return false;// 单层逻辑if(left_tree-val ! right_tree-val) return false;bool b1 dfs(left_tree-left, right_tree-right);bool b2 dfs(left_tree-right, right_tree-left);return b1 b2;
}2.2 另一棵树的子树 Leetcode
分析。子树如果在另一棵树出现过说明另一棵树存在一棵树完全和子树相同我们就只需要看是否有完全相同的树就可以返回值和参数。求是否包含需要由左右子树的状态共同决定返回值bool。求子树是否在另一棵树出现过两个参数(TreeNode* root, TreeNode* subTree)终止条件。特殊情况
if(root nullptr) return false;单层逻辑。当前树是否和子树完全相同如果相同返回true否则看左右子树的情况
if(isSameTree(root, subRoot)) return true;//看左右子树是否相等
return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);这里需要求两棵树是否完全一样isSameTree(TreeNode* p, TreeNode* q)
bool isSameTree(TreeNode* p, TreeNode* q) {if(p nullptr q nullptr) return true;if(p nullptr q ! nullptr) return false;if(p ! nullptr q nullptr) return false;if(p-val ! q-val) return false;bool b1 isSameTree(p-left, q-left);bool b2 isSameTree(p-right, q-right);return b1 b2;
}完整代码
//subRoot是root的子树root中一定有一个树结构和subRoot相等
bool isSubtree(TreeNode* root, TreeNode* subRoot)
{//终止条件if(root nullptr) return false;if(isSameTree(root, subRoot)) return true;//看左右子树是否相等return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);
}bool isSameTree(TreeNode* p, TreeNode* q)
{if(p nullptr q nullptr) return true;else if(p nullptr q ! nullptr) return false;else if(p ! nullptr q nullptr) return false;else if(p-val ! q-val) return false;return isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}2.3 二叉树的最大深度 Leetcode
分析二叉树的最大深度max(左子树深度, 右子树深度) 1返回值和参数。求当前树只需要当前树就可以参数(TreeNode* root)求深度返回值int
int maxDepth(TreeNode* root)终止条件。特殊条件
if(root nullptr) return 0;单层逻辑。确定遍历顺序。因为当前树的情况依赖与左右子树的情况因此需要先遍历左右再处理根节点显然后续。
int left_depth maxDepth(root-left);
int right_depth maxDepth(root-right);return max(left_depth, right_depth) 1;完整代码
int maxDepth(TreeNode* root) {// 终止条件if(root nullptr) return 0;// 单层逻辑int left_depth maxDepth(root-left);int right_depth maxDepth(root-right);return max(left_depth, right_depth) 1;}2.4 二叉树的最小深度 Leetcode
分析最小深度左右子树深度的最小值确定当前当前树的最小深度。但是如果左子树为空那最小深度一定由右子树确定。反之类似。返回值和参数。求当前树只需要当前树就可以参数(TreeNode* root)求深度返回值int终止条件。特殊情况
if(root nullptr) return 0;单层逻辑。想象有三个节点左中右的树当前树的最小深度由左右子树共同确定因此是后序遍历。这里需要注意如果左子树为空那最小深度就是右子树。反之类似。
int left_depth minDepth(root-left);
int right_depth minDepth(root-right);// 左子树为nullptr由右子树确定
if(root-left nullptr) return right_depth 1;
if(root-right nullptr) return left_depth 1;return min(left_depth, right_depth) 1;完整代码
int minDepth(TreeNode* root) {// 终止条件if(root nullptr) return 0;// 单层逻辑int left_depth minDepth(root-left);int right_depth minDepth(root-right);if(root-left nullptr) return right_depth 1;if(root-right nullptr) return left_depth 1;return min(left_depth, right_depth) 1;
}2.5 平衡二叉树 Leetcode
分析。什么是平衡二叉树左子树高度-右子树高度 1因此我们要求左右子树的高度然后比较两者差值返回值和参数。求当前树只需要当前树就可以参数(TreeNode* root)求高度返回值int终止条件。特殊情况
if(root nullptr) return 0;单层逻辑。判断左右子树的高度差1返回-1表示不是平衡的当正常返回高度就是平衡的。这里其实设计到剪枝操作每次不满足条件了我们应该提前返回。
int left_height getHeight(root-left);
if(left_height -1) return -1;
int right_height getHeight(root-right);
if(right_height -1) return -1;if(abs(left_height-right_height) 1) return -1;
else return max(left_height, right_height) 1;完整代码
bool isBalanced(TreeNode* root) {return getHeight(root) -1 ? false : true;}// 左右高度差 1
int getHeight(TreeNode* root) {if(root nullptr) return 0;int left_height getHeight(root-left);if(left_height -1) return -1;int right_height getHeight(root-right);if(right_height -1) return -1;if(abs(left_height-right_height) 1) return -1;else return max(left_height, right_height) 1;
}2.6 完全二叉树的节点个数 Leetcode
分析。完全二叉树是由满二叉树构成如果当前是满二叉树左右子树高度一样那直接就(2 n) - 1然后再计算左右子树的节点数量最后确定当前树的节点数量返回值和参数。求当前树只需要当前树就可以参数(TreeNode* root)求节点个数返回值int
int countNodes(TreeNode* root)终止条件。特殊情况
if(root nullptr) return 0;单层逻辑。当前是树是满二叉树左右子树高度一样直接算(2 n) - 1。否则求左右子树节点数量。
TreeNode* left_tree root-left;
TreeNode* right_tree root-right;
int left_height 0;
int right_height 0;while(left_tree) {left_height;left_tree left_tree-left;
}while(right_tree) {right_height;right_tree right_tree-right;
}if(left_height right_height) {return (2left_height) - 1;
}int c1 countNodes(root-left);
int c2 countNodes(root-right);return c1 c2 1;完整代码 int countNodes(TreeNode* root) {if(root nullptr) return 0;// 当前是不是满二叉树(左子树高度和右子树高度一样)TreeNode* left_tree root-left;TreeNode* right_tree root-right;int left_height 0;int right_height 0;while(left_tree){left_height;left_tree left_tree-left;}while(right_tree){right_height;right_tree right_tree-right;}if(left_height right_height){return (2left_height) - 1;}int c1 countNodes(root-left);int c2 countNodes(root-right);return c1 c2 1;
}2.7 二叉树的所有路径 Leetcode
分析。路径每次从根节点遍历到叶子节点root-left nullptr root-right nullptr时就是一条完整的路径应该记录来。返回值与参数。因为每次递归涉及到当前节点和路径因此参数(TreeNode* root, string path)。这里我们虽然要求所有的路径但是这是整棵树情况相当于是遍历整棵树并不需要左右子树的结果才能推出当前树的结果平衡最大最小深度节点个数都需要左右子树的状态才能确定当前树的状态所以返回值void。这里需要注意我们需要一个全局遍历存最后的结果vectorstring res终止条件。特殊情况
if(root nullptr) return;单层逻辑。当遍历到当前节点并且满足是叶子节点时说明path记录了完整路径需要被记录。否则就需要继续处理左右子树。
if(root nullptr) return;// 每次进来先把当前节点的值加入到路径
path to_string(root-val);if(root-left nullptr root-right nullptr)
{res.push_back(path);
}//这里已经回溯过了
dfs(root-left, path -);
dfs(root-right, path -);完整代码
vectorstring res;vectorstring binaryTreePaths(TreeNode* root)
{if(root nullptr) return res;string path ;dfs(root, path);return res;
}void dfs(TreeNode* root, string path)
{if(root nullptr) return;path to_string(root-val);if(root-left nullptr root-right nullptr){res.push_back(path);}//这里已经回溯过了dfs(root-left, path -);dfs(root-right, path -);
}2.8 路径总和 Leetcode
分析。路径每次从根节点遍历到叶子节点root-left nullptr root-right nullptr时就是一条完整的路径此时需要看targetNum是否刚好0刚好等于0说明这条路径上的和就是targetNum返回值和参数。是否满足条件并且当前树的情况和左右子树的状态都有关系返回值bool。参数当前树有无满足路径和为targetNum的因此需要两个参数(TreeNode* root, int targetNum)。终止条件。特殊情况
if(root nullptr) return false;单层逻辑。如果当前节点是叶子节点说明已经找到一条路径判断targetNum是否是0是就返回true否则还需要看左右子树的状态
// 先记录当前值
targetSum - root-val;
if(root-left nullptr root-right nullptr)
{if(targetSum 0){return true;}
}bool b1 hasPathSum(root-left, targetSum);
if(b1) return true;bool b2 hasPathSum(root-right, targetSum);
if(b2) return true;return false;完整代码
bool hasPathSum(TreeNode* root, int targetSum) {
if(root nullptr) return false;targetSum - root-val;
if(root-left nullptr root-right nullptr)
{if(targetSum 0){return true;}
}bool b1 hasPathSum(root-left, targetSum);
if(b1) return true; // 一个剪枝操作bool b2 hasPathSum(root-right, targetSum);
if(b2) return true;return false;
}2.9 左叶子之和 Leetcode
分析。什么是左叶子root-left root-left-left nullptr root-left-right nullptr说明root-left就是左叶子返回值和参数。求做左叶子之和当前节点依赖于左右子树的状态返回值int。求当前树参数(TreeNode* root)终止条件。特殊情况
if(root nullptr) return 0;单层逻辑。找当前节点的左叶子然后再找左右子树的做叶子之和。
// 当前节点的左叶子节点
int curValue 0;
if(root-left root-left-left nullptr root-left-right nullptr)
{ curValue root-left-val;
}int s1 sumOfLeftLeaves(root-left);
int s2 sumOfLeftLeaves(root-right);return s1 s2 curValue;完整代码
int sumOfLeftLeaves(TreeNode* root) {if(root nullptr) return 0;
// 当前节点的左叶子节点
int curValue 0;
if(root-left root-left-left nullptr root-left-right nullptr)
{ curValue root-left-val;
}int s1 sumOfLeftLeaves(root-left);
int s2 sumOfLeftLeaves(root-right);return s1 s2 curValue;}2.10 找树左下角的值 Leetcode
分析。左下角的值最深的一层的第一个节点。因此需要一个变量记录树当前的最大深度max_depth返回值与参数。找最左下角的值但是当前树最左下的值和左右子树的状态没有关系返回值void。要判断当前节点的深度是不是最大深度因此有两个参数(TreeNode* root, int depth)终止条件。特殊情况
if(root nullptr) return;单层逻辑。遍历到叶子节点时如果该叶子节点所在深度大于max_depth说明该叶子节点是当前层的第一个节点左叶子节点。没找到就继续在左右子树找
if(root-left nullptr root-right nullptr)
{if(depth max_depth) {res root-val;max_depth depth;}
}dfs(root-left, depth1);
dfs(root-right, depth1);完整代码
int max_depth INT_MIN;
int res 0;
int findBottomLeftValue(TreeNode* root) {if(root nullptr) return 0;dfs(root, 1);return res;
}void dfs(TreeNode* root, int depth)
{if(root nullptr) return;if(root-left nullptr root-right nullptr){if(depth max_depth) {res root-val;max_depth depth;}}dfs(root-left, depth1);dfs(root-right, depth1);
}3. 二叉树的修改与构造
3.1 翻转二叉树 Leetcode
分析。要想翻转一棵二叉树先翻转左右子树先翻转当前节点左右子树明显是后序返回值和参数。要求翻转后的二叉树并且当前树的状态和左右子树有关系因此返回值TreeNode*。求当前树参数(TreeNode* root)终止条件。特殊情况
if(root nullptr) return nullptr;单层逻辑。先翻转左右子树先翻转当前节点左右子树。
TreeNode* left_tree invertTree(root-left);
TreeNode* right_tree invertTree(root-right);root-left right_tree;
root-right left_tree;return root;完整代码
TreeNode* invertTree(TreeNode* root) {
if(root nullptr) return nullptr;TreeNode* left_tree invertTree(root-left);
TreeNode* right_tree invertTree(root-right);root-left right_tree;
root-right left_tree;return root;
}3.2 从中序与后序遍历序列构造二叉树 Leetcode
分析。后序左右中中序左中右。我们可以在后序中找到中间节点最后一个然后再根据该节点划分中序分成左中右三个部分然后就可以递归处理左右。返回值和参数。要求构造的二叉树当前树和左右子树的状态有关系返回值TreeNode*。我们每次要确定中序和后序的左右边界一个好的想法是直接在参数中表明因此参数(vectorint inorder, int inStart, int inEnd, vectorint postorder, int postStart, int postEnd)。终止条件。特殊情况
if(inStart inEnd) return nullptr;单层逻辑。先在后序找到中节点再根据中节点将中序划分为左中右最后递归处理左右子树
//在前序找中
int mid_val postorder[postEnd - 1];
TreeNode* root new TreeNode(mid_val);//在中序找中
int mid_idx 0;
for(int i inStart; iinEnd; i)
{if(inorder[i] mid_val){mid_idx i;break;}
}//左子树
int inLeftStart inStart;
int inLeftEnd mid_idx;
int postLeftStart postStart;
int postLeftEnd postStart mid_idx - inStart;
TreeNode* left_tree dfs(inorder, inLeftStart, inLeftEnd, postorder, postLeftStart, postLeftEnd);//右子树
int inRightStart inLeftEnd 1;
int inRightEnd inEnd;
int postRightStart postLeftEnd;
int postRightEnd postEnd - 1;
TreeNode* right_tree dfs(inorder, inRightStart, inRightEnd, postorder, postRightStart, postRightEnd);root-left left_tree;
root-right right_tree;return root;完整代码
TreeNode* buildTree(vectorint inorder, vectorint postorder) {return dfs(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}TreeNode* dfs(vectorint inorder, int inStart, int inEnd, vectorint postorder, int postStart, int postEnd)
{if(inStart inEnd) return nullptr;//在前序找中int mid_val postorder[postEnd - 1];TreeNode* root new TreeNode(mid_val);//在中序找中int mid_idx 0;for(int i inStart; iinEnd; i){if(inorder[i] mid_val){mid_idx i;break;}}//左子树int inLeftStart inStart;int inLeftEnd mid_idx;int postLeftStart postStart;int postLeftEnd postStart mid_idx - inStart;TreeNode* left_tree dfs(inorder, inLeftStart, inLeftEnd, postorder, postLeftStart, postLeftEnd);//右子树int inRightStart inLeftEnd 1;int inRightEnd inEnd;int postRightStart postLeftEnd;int postRightEnd postEnd - 1;TreeNode* right_tree dfs(inorder, inRightStart, inRightEnd, postorder, postRightStart, postRightEnd);root-left left_tree;root-right right_tree;return root;
}3.3 最大二叉树 Leetcode
分析。先找到最大值再划分左右子树递归处理左右子树返回值和参数。求构造的最大二叉树并且当前树依赖于左右节点状态返回值TreeNode*。确定当前处理的区间参数·(vectorint nums, int start, int end)终止条件。特殊情况
if(start end) return nullptr;单层逻辑。先找到最大值再划分左右子树递归处理左右子树
//找到最大值
int max_val INT_MIN;
int max_idx -1;
for(int i start; iend; i)
{if(nums[i] max_val){max_val nums[i];max_idx i;}
}TreeNode* root new TreeNode(max_val);//左
int leftStart start;
int leftEnd max_idx;
TreeNode* left_tree dfs(nums, leftStart, leftEnd);
//右
int rightStart leftEnd 1;
int rightEnd end;
TreeNode* right_tree dfs(nums, rightStart, rightEnd);root-left left_tree;
root-right right_tree;return root; 3.4 合并二叉树 Leetcode
分析。如果两棵树都不是null把root2合并到root1上。先处理当前节点然后处理左右子树。返回值和参数。求合并后的二叉树并且当前树和左右子树的状态有关系因此返回值TreeNode*。合并两个数参数(TreeNode* root1, TreeNode* root2)终止条件。当任意一棵树为null返回另一棵树
if(root1 nullptr) return root2;
if(root2 nullptr) return root1;单层逻辑。如果两棵树都不是null把root2合并到root1上。先处理当前节点然后处理左右子树。
root1-val root1-val root2-val;TreeNode* left_tree mergeTrees(root1-left, root2-left);
TreeNode* right_tree mergeTrees(root1-right, root2-right);root1-left left_tree;
root1-right right_tree;return root1;完整代码
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 nullptr) return root2;if(root2 nullptr) return root1;root1-val root1-val root2-val;TreeNode* left_tree mergeTrees(root1-left, root2-left);TreeNode* right_tree mergeTrees(root1-right, root2-right);root1-left left_tree;root1-right right_tree;return root1;
}
