fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
东哥带你刷二叉树（思路篇） :: labuladong的算法小抄
东哥，这里我一直搞不懂。
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
@Jiujiale
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
这段就是让原右子树接到原左子树的末尾
- 具体到这张图的话, 也就是让
5接到4后面 - 如果不用
while循环, 则5会直接接到2的后面, 这样点话3和4就丢失了
116题根据你的思路，我想的是另一种思路：
class Solution {
public:
Node* connect(Node* root) {
if(root==nullptr){
return root;
}
root->next = nullptr;
DFS(root);
return root;
}
void DFS(Node* node){
if(node==nullptr || node->left==nullptr){
return ;
}
node->left->next = node->right;
if(node->next!=nullptr){
node->right->next = node->next->left;
}
DFS(node->left);
DFS(node->right);
}
};
TreeNode left = root.left;
TreeNode right = root.right;
上面两行能将左右链表从root上剪枝下来吗？不能的话
下面两句不是会把左边的链表接到右边链表后面吗？
root.left = null;
root.right = left;
@huangpan2507 明白了，是直接从root将右子节点后面接上 保存的root.left.相当于把原本的右节点内容踹了。接上了左边的链表
我的解法是先嫁接到左节点：
private void dfs(TreeNode node) {
if (node == null) {
return;
}
dfs(node.left);
dfs(node.right);
TreeNode left = node.left;
TreeNode right = node.right;
// 寻找左子树中最后一个右节点
TreeNode lastNodeOfLeftTree = left;
while (lastNodeOfLeftTree != null && lastNodeOfLeftTree.right != null) {
lastNodeOfLeftTree = lastNodeOfLeftTree.right;
}
node.left = null;
// 左节点不为空的时候才嫁接右节点过去；左节点为空的时候，右节点就不动
if (lastNodeOfLeftTree != null) {
lastNodeOfLeftTree.right = right;
node.right = left;
}
}
东哥的解题方法，神赞！ 我特意当当去买了你的算法小抄书，但是不知道怎么把书上的顺序和这个网站对应起来，比如这里说的leetcode116， 我在书上没找到呀。
第二个问题，leetcode 116，我用你的方法但是python写出来，一直有编译报错问题，东哥或者其它学友麻烦帮忙看下？
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
# Base Case
if root is None:
return root
connectTwoNode(root.left, root.right)
return root
def connectTwoNode(self, node1, node2):
if node1 is None or node2 is None:
return
node1.next = node2
self.connectTwoNode(node1.left, node1.right)
self.connectTwoNode(node2.left, node2.right)
self.connectTwoNode(node1.right, node2.left)
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
# Base Case
if root is None:
return root
connectTwoNode(root.left, root.right)
return root
# Preorder
def connectTwoNode(self, node1, node2):
if node1 is None or node2 is None:
return
node1.next = node2
self.connectTwoNode(node1.left, node1.right)
self.connectTwoNode(node2.left, node2.right)
self.connectTwoNode(node1.right, node2.left)
// 辅助函数
void connectTwoNode(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
116题，这个 if 判断，因为是完美二叉树，就代表只要 node1 不是 null，node2 就不是 null，反之，node1 只要是 null，node2 也一定是 null，所以 只需要判断 node1 是否为 null 即可满足条件。
我是这么理解的，提交也通过了，东哥我理解的对不？
114题，既然递归是无敌，何必用while在进入到子串内部呢?
class Solution {
public void flatten(TreeNode root) {
flatten1(root);
}
public TreeNode flatten1(TreeNode root) {
if(root==null){
return null;
}
//获取尾部节点
TreeNode endl=flatten1(root.left);
TreeNode endr=flatten1(root.right);
//获取尾部为空时
if(endl==null&&endr==null){
return root;
}else if(endl==null){
return endr;
}else if(endr==null){
root.right=root.left;
root.left=null;
return endl;
}
//右串接入左串尾部，左串接入右边
endl.right=root.right;
root.right=root.left;
root.left=null;
return endr;
}
}
class Solution {
public:
void flatten(TreeNode* root) {
if(root == nullptr)
return;
TreeNode* left = root->left;
TreeNode* right = root->right;
root->right = left;
root->left = nullptr;
TreeNode* p = root;
while (p->right)
{
p = p->right;
}
p->right = right;
flatten(root->left);
flatten(root->right);
//
}
};
前序应该也可以，核心思路都是将左节点放到右节点； 旧的右节点，再挂载到当前右节点最下面；
大佬，116题有个不同的解法，就是根据当前节点的父节点的next节点（如果存在的话），就可以找到他的跨节点的
public static TreeNode connect(TreeNode node) {
//判断node的right和或者left不为空即可
if(node.getLeft() == null) {
return node;
}
TreeNode left = node.getLeft();
TreeNode right = node.getRight();
//先把节点内的next搞定
left.setNext(right);
//对于跨节点的，根据当前节点的父节点的next（如果next存在的话）,就能找到他的跨节点
TreeNode next = node.getNext();
if(next != null) {
right.setNext(next.getLeft());
}
connect(left);
connect(right);
return node;
}
第二题、填充二叉树节点的右侧指针,
connectTwoNode(node1.left, node1.right); connectTwoNode(node2.left, node2.right); connectTwoNode(node1.right, node2.left);
这样子有些事情重复做了，想node1.right 和 node2.left 的子节点，就会重复处理，结果也没什么不同，但分析时间就变得复杂了。
js 版节点翻转
function invertTree(root) {
// base case
if (root === null) {
return null;
}
/**** 前序遍历位置 ****/
// root 节点需要交换它的左右子节点
[root.left, root.right] = [root.right, root.left];
// 让左右子节点继续翻转它们的子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
js 版填充右侧指针
var connect = function(root) {
if (root === null) {
return root;
}
connectTwoNode(root.left, root.right);
return root;
function connectTwoNode(node1, node2) {
if (node1 === null || node2 === null) {
return;
}
/**** 前序遍历位置 ****/
// 将传入的两个节点连接
node1.next = node2;
// 连接相同父节点的两个子节点
connectTwoNode(node1.left, node1.right);
connectTwoNode(node2.left, node2.right);
// 连接跨越父节点的两个子节点
connectTwoNode(node1.right, node2.left);
}
};
js 版树展链表
var flatten = function (root) {
if (root === null) {
return root;
}
flatten(root.left);
flatten(root.right);
/**** 后序遍历位置 ****/
// 1、左右子树已经被拉平成一条链表
const left = root.left;
const right = root.right;
root.left = null;
root.right = left;
// 3、将原先的右子树接到当前右子树的末端
let p = root;
while (p.right !== null) {
p = p.right;
}
p.right = right;
return root;
};
不过我感觉第二题 填充右侧指针 更直观的做法是BFS吧，虽然有点空间开销。 我写出来的BFS版本是这样的
var connect = function (root) {
if (root === null) {
return root;
}
const q = [root];
// bfs 逐层遍历
while (q.length) {
const sz = q.length; // 当前层的节点数
for (let i = 0; i < sz; i++) {
const node = q.shift();
// 连接节点，如果是最后一个节点，则置 null
node.next = i === sz - 1 ? null : q[0];
// 准备下一层
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return root;
};
114题直接先序遍历也行吧
class Solution {
public:
TreeNode *pre = nullptr;
void flatten(TreeNode* root) {
if (root == nullptr) return;
auto l = root->left;
auto r = root->right;
if (pre) { pre->right = root; pre->left = nullptr; }
pre = root;
flatten(l);
flatten(r);
}
};
"你看，这就是递归的魅力，你说 flatten 函数是怎么把左右子树拉平的？说不清楚，但是只要知道 flatten 的定义如此，相信这个定义，让 root 做它该做的事情，然后 flatten 函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。"
这个解释好玄学呀....
感觉翻转二叉树直接这么写更简洁一些：
TreeNode* invertTree(TreeNode* root) {
// base case
if (root == nullptr) return nullptr;
// recursive
// since we only change pointer direction ,when saving root->left, we mean saving all its successor relationship
TreeNode* tempLeft = root->left;
root->left = invertTree(root->right);
root->right = invertTree(tempLeft);
return root;
}
