current position:Home>1379. Find the same node in the cloned binary tree (Java / C + + / Python)
1379. Find the same node in the cloned binary tree (Java / C + + / Python)
2022-01-31 17:42:08 【White hat of the second leader】
This is my participation 11 The fourth of the yuegengwen challenge 9 God , Check out the activity details :2021 One last more challenge
Thank you very much for reading this article ~
welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~
It's not hard to give up , But persistence must be cool ~
I hope all of us can make a little progress every day ~
This paper is written by The white hat of the second leader :https://juejin.cn/user/2771185768884824/posts Original blog ~
1379. Find the same node in the clone binary tree :
Here are two binary trees , Primitive tree original
And clone trees cloned
, And one in the original tree original
Target node in target
.
among , Clone tree cloned
It's a primitive tree original
One of the copy .
Please find the tree cloned
in , And target
identical The node of , And return a reference to the node ( stay C/C++ Return... In a language with a pointer Node pointer , Other languages return the node itself ).
Be careful :
- you You can't For two binary trees , as well as
target
Make changes to the node . - Can only Return to the clone tree
cloned
References to existing nodes in .
Advanced : If nodes with the same value are allowed in the tree , How will you answer ?
Examples 1:
Input :
tree = [7,4,3,null,null,6,19], target = 3
Output :
3
explain :
The picture above shows the tree original and cloned.target Nodes in the tree original in , Mark it in green . The answer is trees cloned Yellow nodes in ( Other examples are similar ).
Copy code
Examples 2:
Input :
tree = [7], target = 7
Output :
7
Copy code
Examples 3:
Input :
tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output :
4
Copy code
Examples 4:
Input :
tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output :
5
Copy code
Examples 5:
Input :
tree = [1,2,null,3], target = 2
Output :
2
Copy code
Tips :
- The number of nodes in the tree ranges from [1, 104] .
- In the same tree , There are no nodes with the same value .
target
Nodes are treesoriginal
One of the nodes in , And it won't benull
.
analysis
- This algorithm problem needs a simple translation , Three parameters : The first parameter
original
It's the original tree ; The second parametercloned
Is a clone copy of the first parameter ; The third parametertarget
Is the node we want to find , It is the first parameteroriginal
One of the nodes in , You need to find and return the second parametercloned
The corresponding node in . - The hint says that in the same tree , There are no nodes with the same value . Therefore, some small partners may feel that the first parameter is very redundant , The second leader thinks so . We directly iterate over the second parameter
cloned
, Until you find and the third parametertarget
Just return a node with the same value . - In fact, the first parameter is Advanced It's useful in the challenge , If nodes with the same value are allowed in the tree , Then you can't judge the same node by value .
- In this case, you need to use the first parameter
original
, Because the third parametertarget
Is a node in the original tree , So we can directly judge whether it is the same node according to the address . - The second parameter
cloned
Is a clone copy of the first parameter , So they have the same structure , We just traverse the original tree and clone tree in the same order , You can find the answer .
Answer key
java
Non recursive traversal
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = original;
TreeNode clonedNode = cloned;
while (node != null || !stack.isEmpty()) {
if (node != null) {
if (node == target) {
return clonedNode;
}
stack.push(clonedNode);
stack.push(node);
node = node.left;
clonedNode = clonedNode.left;
} else {
node = stack.pop().right;
clonedNode = stack.pop().right;
}
}
return null;
}
}
Copy code
Recursive traversal
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
if (cloned == null
|| original == target) {
return cloned;
}
TreeNode ans = getTargetCopy(original.left, cloned.left, target);
if (ans == null) {
ans = getTargetCopy(original.right, cloned.right, target);
}
return ans;
}
}
Copy code
c++
/** * 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* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
if (cloned == nullptr
|| original == target) {
return cloned;
}
TreeNode* ans = getTargetCopy(original->left, cloned->left, target);
if (ans == nullptr) {
ans = getTargetCopy(original->right, cloned->right, target);
}
return ans;
}
};
Copy code
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
if cloned is None or original == target:
return cloned
ans = self.getTargetCopy(original.left, cloned.left, target)
if ans is None:
ans = self.getTargetCopy(original.right, cloned.right, target)
return ans
Copy code
Original title transmission gate :https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/
copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311742072760.html
The sidebar is recommended
- Python - convert Matplotlib image to numpy Array or PIL Image
- Python and Java crawl personal blog information and export it to excel
- Using class decorators in Python
- Untested Python code is not far from crashing
- Python efficient derivation (8)
- Python requests Library
- leetcode 2047. Number of Valid Words in a Sentence(python)
- leetcode 2027. Minimum Moves to Convert String(python)
- How IOS developers learn Python Programming 5 - data types 2
- leetcode 1971. Find if Path Exists in Graph(python)
guess what you like
-
leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores(python)
-
Python interface automation test framework (basic) -- basic syntax
-
Detailed explanation of Python derivation
-
Python reptile lesson 2-9 Chinese monster database. It is found that there is a classification of color (he) desire (Xie) monsters during operation
-
A brief note on the method of creating Python virtual environment in Intranet Environment
-
[worth collecting] for Python beginners, sort out the common errors of beginners + Python Mini applet! (code attached)
-
[Python souvenir book] two people in one room have three meals and four seasons: 'how many years is it only XX years away from a hundred years of good marriage' ~?? Just come in and have a look.
-
The unknown side of Python functions
-
Python based interface automation test project, complete actual project, with source code sharing
-
A python artifact handles automatic chart color matching
Random recommended
- Python crawls the map of Gaode and the weather conditions of each city
- leetcode 1275. Find Winner on a Tic Tac Toe Game(python)
- leetcode 2016. Maximum Difference Between Increasing Elements(python)
- Run through Python date and time processing (Part 2)
- Application of urllib package in Python
- Django API Version (II)
- Python utility module playsound
- Database addition, deletion, modification and query of Python Sqlalchemy basic operation
- Tiobe November programming language ranking: Python surpasses C language to become the first! PHP is about to fall out of the top ten?
- Learn how to use opencv and python to realize face recognition!
- Using OpenCV and python to identify credit card numbers
- Principle of Python Apriori algorithm (11)
- Python AI steals your voice in 5 seconds
- A glance at Python's file processing (Part 1)
- Python cloud cat
- Python crawler actual combat, pyecharts module, python data analysis tells you which goods are popular on free fish~
- Using pandas to implement SQL group_ concat
- How IOS developers learn Python Programming 8 - set type 3
- windows10+apache2. 4 + Django deployment
- Django parser
- leetcode 1560. Most Visited Sector in a Circular Track(python)
- leetcode 1995. Count Special Quadruplets(python)
- How to program based on interfaces using Python
- leetcode 1286. Iterator for Combination(python)
- leetcode 1418. Display Table of Food Orders in a Restaurant (python)
- Python Matplotlib drawing histogram
- Python development foundation summary (VII) database + FTP + character coding + source code security
- Python modular package management and import mechanism
- Django serialization (II)
- Python dataloader error "dataloader worker (PID XXX) is killed by signal" solution
- apache2. 4 + Django + windows 10 Automated Deployment
- leetcode 1222. Queens That Can Attack the King(python)
- leetcode 1387. Sort Integers by The Power Value (python)
- Tiger sniffing 24-hour praise device, a case with a crawler skill, python crawler lesson 7-9
- Python object oriented programming 01: introduction classes and objects
- Baidu Post: high definition Python
- Python Matplotlib drawing contour map
- Python crawler actual combat, requests module, python realizes IMDB movie top data visualization
- Python classic: explain programming and development from simple to deep and step by step
- Python implements URL availability monitoring and instant push