树的子结构之先序遍历+二叉树的镜像+对称二叉树

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

树的子结构之先序遍历+二叉树的镜像+对称二叉树

2023-02-16 12:12:44 来源：博客园

问题1：树的子结构剑指 Offer 26. 树的子结构 - 力扣（LeetCode）

(资料图片仅供参考)

思路：先序遍历

isSubtree函数：遍历一遍a树的每一个节点，找到与b树匹配的根节点，即调用recur函数；

否则递归调用自身，找下一个匹配的根节点。

recur函数返回条件：直到遍历完b树则成功，或者a树遍历完失败，或者节点不相等失败；

否则说明相等，继续递归下一个左右子节点，并且是逻辑与的关系

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    bool isSubStructure(TreeNode* A, TreeNode* B) {        if(A == nullptr || B == nullptr) return false;        return recur(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);    }private:    bool recur(TreeNode* a , TreeNode* b){        if(b == nullptr) return true;        if(a == nullptr) return false;        if(a->val != b->val) return false;        return recur(a->left,b->left) && recur(a->right,b->right);    }};

问题2：二叉树的镜像剑指 Offer 27. 二叉树的镜像（递归 / 辅助栈，清晰图解） - 二叉树的镜像 - 力扣（LeetCode）

思路：递归，从当前根节点开始，若为空，直接返回；

递归根节点的左子节点，一路递归下去，直到叶子节点为空返回本身，跳出最后一次的递归，接着执行右子节点镜像，也是返回本身，

交换当前两节点，（处于子树的末梢的两节点）；

返回这两节点的父节点，跳出当前的递归，接着又执行这个父节点的右子节点，如此循环；

时间复杂度：O(N) ; 空间复杂度：O(N),递归栈的深度。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    TreeNode* mirrorTree(TreeNode* root) {        if(root == nullptr) return nullptr;        TreeNode* left = mirrorTree(root->left);        TreeNode* right = mirrorTree(root->right);        root->left = right;        root->right = left;        return root;    }};

关键词：空间复杂度时间复杂度