上次编辑到这里，代码来自缓存 点击恢复默认模板
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
};
*/
class Solution {
public:
Node* flipBinaryTree(Node* root, Node * leaf) {
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-21 22:55:50
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def flipBinaryTree(self, root: 'Node', leaf: 'Node') -> 'Node':
#像是在维持一个双向链表 题意读不懂。根据实例猜的
if root == leaf:
return root
leaf.left = leaf.parent
leaf.parent = None
p = leaf
while p.left != root:
if p.left.right == p: #7是5的右子
p.left.right = p.left.left #5的右子是原来5的左子
p.left.left = p.left.parent #5的左子是3
p.left.parent = p #5的父是7
p = p.left
if p.left.left == p: #此时，p.left = root
p.left.left = None
else: #若p是root的右子
p.left.right = None
p.left.parent = p #root的福父节点是p
return leaf
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.8 MB, 提交时间: 2023-10-21 22:55:07
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
};
*/
class Solution {
public:
Node* flipBinaryTree(Node* root, Node * leaf) {
if (root == leaf)
return root;
leaf -> left = leaf->parent;
leaf->parent = NULL;
Node* p = leaf;
while (p->left != root) { //5不是根
if (p->left->right == p) //7是5的右子
p->left -> right = p->left->left; //6要变成5的右子
p->left -> left = p->left->parent; //5的左子成了3
p->left -> parent = p; //5的父成了7
p = p->left; //7要往上走，到了5的位置。
}
if (p->left->left == p) //是root的左子
p->left -> left = NULL;
else //是root的右子
p->left->right = NULL;
p->left->parent = p; //root的父变成了leaf
return leaf;
}
};
java 解法, 执行用时: 12 ms, 内存消耗: 39.9 MB, 提交时间: 2023-10-21 22:54:35
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/
class Solution {
private Node root;
public Node flipBinaryTree(Node root, Node leaf) {
this.root = root;
flipBinaryTreeHelper(leaf);
leaf.parent = null;
return leaf;
}
private void flipBinaryTreeHelper(Node cur) {
if (cur == root) return;
Node left = cur.left;
Node parent = cur.parent;
if (cur.left != null) {
cur.right = left;
}
cur.left = parent;
if (parent.left == cur) parent.left = null;
if (parent.right == cur) parent.right = null;
flipBinaryTreeHelper(parent);
parent.parent = cur;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-21 22:52:18
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
# 递归
def flipBinaryTree(self, root: 'Node', leaf: 'Node') -> 'Node':
if leaf == root:
return leaf
if leaf.left:
leaf.right = leaf.left
if leaf.parent:
if leaf is leaf.parent.left:
leaf.parent.left = None
elif leaf is leaf.parent.right:
leaf.parent.right = None
leaf.left = self.flipBinaryTree(root, leaf.parent)
if leaf.left:
leaf.left.parent = leaf
leaf.parent = None
return leaf
# dfs
def flipBinaryTree2(self, root: 'Node', leaf: 'Node') -> 'Node':
self.root = root
self.res = leaf
self.dfs(leaf.parent,leaf,None)
return self.res
def dfs(self,p,leaf,np):
if not p:
return None
gp = p.parent
if p.left == leaf:
p.left = None
else:
if p==self.root:
p.right = None
else:
p.right = p.left
p.left = None
p.parent = leaf
leaf.left = p
leaf.parent = np
