Powered by:NEFU AB-IN

Link

1379. 找出克隆二叉树中的相同节点

• 题意

  给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
  其中，克隆树 cloned 是原始树 original 的一个 副本 。
  请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。

• 思路

  DFS找值即可，这里提供两个DFS版本

  • 第一版是返回void的DFS
  • 第二版是直接返回结果的

• 代码

  版本1

  /**
  * 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* ans = new TreeNode();
      void dfs(TreeNode* root, int val){
          if(!root) return;
          
          if(root->val == val){
              ans = root;
              return;
          }    
          dfs(root->left, val);
          dfs(root->right, val);
      }
      TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
          
          dfs(cloned, target->val);
          return ans;
      }
  };
  

  ---

  版本2

  /**
  * 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* dfs(TreeNode* root, int val){
          if(!root) return nullptr;
          if(root->val == val){
              return root;
          }    
          auto left = dfs(root->left, val); // 先把值记下来，如果不空再返回
          if(left) return left;
          auto right = dfs(root->right, val);
          if(right) return right;
          
          return nullptr;
      }
      TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
          return dfs(cloned, target->val);
      }
  };