二叉树中某一值的路径之先序遍历 + 二叉搜索树转化为循环双向链表之中序遍历

手机

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

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

家电

二叉树中某一值的路径之先序遍历 + 二叉搜索树转化为循环双向链表之中序遍历

2023-02-16 21:59:05 来源：博客园

问题：二叉树中某一值的路径之先序遍历剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode）

思路：先序遍历递归

(相关资料图)

返回：碰到叶子节点，为nullptr，直接返回；

递推：将当前节点加入路径vector；目标值更新；路径判定-当此节点为叶子节点，并且目标值为0；则将此vector 加入外层vector；

递归当前节点的左右子节点；

回溯：路径vector 需要pop_back()这个节点，再向前回溯

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector> pathSum(TreeNode* root, int target) {        recur(root,target);        return paths;    }private:    vectorload;    vector>paths;    void recur(TreeNode* root,int target){        if(root == nullptr) return;        load.push_back(root->val);        target -= root->val;        if(target == 0 && root->left == nullptr && root->right == nullptr) paths.push_back(load);        recur(root->left,target);        recur(root->right,target);        load.pop_back();    }};

问题：二叉搜索树转化为循环双向链表之中序遍历

思路：先序遍历+递归

定义两节点，一个头节点和节点pre，

先递归遍历左子树的左节点；第一次递归到最小的左节点， pre为空，将cur赋值为head；建立双向联系；将cur节点赋值为pre；递归右子节点；

终止：碰到叶子节点nullptr，直接返回

最终将头节点和尾节点pre建立双向联系。

/*// Definition for a Node.class Node {public:    int val;    Node* left;    Node* right;    Node() {}    Node(int _val) {        val = _val;        left = NULL;        right = NULL;    }    Node(int _val, Node* _left, Node* _right) {        val = _val;        left = _left;        right = _right;    }};*/class Solution {public:    Node* treeToDoublyList(Node* root) {        if(root == nullptr)  return nullptr;        dfs(root);        head->left = pre;        pre -> right = head;        return head;    }private:    Node* head,*pre;    void dfs(Node* cur){        if(cur == nullptr) return;        dfs(cur->left);        if(pre == nullptr) head = cur;        else pre->right = cur;        cur -> left = pre;        pre = cur;        dfs(cur -> right);    }};

关键词：双向链表

二叉树中某一值的路径之 先序遍历 + 二叉搜索树转化为循环双向链表 之 中序遍历

二叉树中某一值的路径之先序遍历 + 二叉搜索树转化为循环双向链表之中序遍历