东哥带你刷二叉树（思路篇） :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：东哥带你刷二叉树（思路篇）

评论礼仪 见这里，违者直接拉黑。

[jiaqiu-09]

东哥，这里我一直搞不懂。

// 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }

[yxw007]

这里就是链表找最后一个节点啊，有啥不懂？

[ArmandXiao]

@Jiujiale

// 3、将原先的右子树接到当前右子树的末端
   TreeNode p = root;
   while (p.right != null) {
       p = p.right;
   }

这段就是让原右子树接到原左子树的末尾

• 具体到这张图的话, 也就是让5接到4后面
• 如果不用while循环, 则5会直接接到2的后面, 这样点话3和4就丢失了

[labuladong]

@ArmandXiao 说的对，其实这题有效率更高的方式，利用二叉树的遍历顺序从而避免 while 循环，不过略难理解。 @Jiujiale

[lj110107]

可以定义函数返回该子树对应的last节点一直向上传，就不用while循环了

[fear666]

按东哥的思路“利用二叉树的遍历顺序从而避免 while 循环” NICE!

golang打卡

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    if root == nil {
        return
    }
    traverse(root)
}

func traverse(node *TreeNode) (*TreeNode, *TreeNode) { //返回拉平后的链表的头节点、尾节点
    if node.Left == nil && node.Right == nil { //叶子
        return node, node
    } else if node.Left == nil { //该节点只有右子树
        _,rt := traverse(node.Right)
        return node,rt
    } else if node.Right == nil { //该节点只有左子树
        lh,lt := traverse(node.Left)
        node.Right = lh
        node.Left = nil
        return node, lt
    }

    lh,lt := traverse(node.Left)
    rh,rt := traverse(node.Right)
    
    //置空当前节点的左边，拼接左右子链表并放置到当前节点的右边
    node.Left = nil
    node.Right = lh
    lt.Right = rh

    return node,rt
}

[jiaqiu-09]

多谢两位指点 @ArmandXiao @labuladong

[DefuLi]

翻转二叉树这个题，中序遍历会对原左节点翻转两次。

[buddy-source]

知道怎么改吗

[gloom2003]

public TreeNode invertTree(TreeNode root) {
       if(root == null){
           return null;
       }
       invertTree(root.left);
       //中序遍历位置
       TreeNode temp = root.left;
       root.left = root.right;
       root.right = temp;
       //root.right改为root.left,因为invertTree(root.left)执行完后左右子树交换了
       invertTree(root.left);
       return root;
   }

[RockRockWhite]

讲的太好了！！！
看完这一篇感觉就理解递归了。
相信函数定义，跳出函数本身。

[zbf1-999]

哈哈哈哈 相信相信的力量

[gloom2003]

public TreeNode invertTree(TreeNode root) {
       if(root == null){
           return null;
       }
       invertTree(root.left);
       //中序遍历位置
       TreeNode temp = root.left;
       root.left = root.right;
       root.right = temp;
       //root.right改为root.left,因为invertTree(root.left)执行完后左右子树交换了
       invertTree(root.left);
       return root;
   }

[hui60]

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);
    }
};

[huangpan2507]

TreeNode left = root.left;
TreeNode right = root.right;
上面两行能将左右链表从root上剪枝下来吗？不能的话
下面两句不是会把左边的链表接到右边链表后面吗？
root.left = null;
root.right = left;

[huangpan2507]

@huangpan2507 明白了，是直接从root将右子节点后面接上 保存的root.left.相当于把原本的右节点内容踹了。接上了左边的链表

[tinyhare]

第三题，为什么我默写的时候思维总是那么别扭。想的是先把右侧接到左侧，然后把左侧接到根上，这样需要判断左侧是否是null。

[linhualuo]

我的解法是先嫁接到左节点：

        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;
            }
        }

[zhli-hub]

东哥牛逼！

[canacexue]

东哥的解题方法，神赞！
我特意当当去买了你的算法小抄书，但是不知道怎么把书上的顺序和这个网站对应起来，比如这里说的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)

[191086]

函数嵌套了，里面的函数不能用self

[wy-luke]

// 辅助函数
void connectTwoNode(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }

116题，这个 if 判断，因为是完美二叉树，就代表只要 node1 不是 null，node2 就不是 null，反之，node1 只要是 null，node2 也一定是 null，所以 只需要判断 node1 是否为 null 即可满足条件。

我是这么理解的，提交也通过了，东哥我理解的对不？

[bald9]

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;
    }
}

[191086]

第二题可以使用层序遍历的方法，里面while循环里面两个for循环，一个负责next指针，一个和原层序遍历一样

[Andywjw]

hhy必进大厂

[kanghsieh11]

114题提供一种遍历思路，遍历函数返回子树先序序列的最后一个节点

class Solution {

    TreeNode* traversal(TreeNode* root)
    {
        if (root == nullptr) 
            return root;
        TreeNode* endL = traversal(root->left);
        TreeNode* endR = traversal(root->right);
        if (endL != nullptr)
        {
            endL->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }

        return endR ? endR : endL ? endL : root;
    }

public:
    void flatten(TreeNode* root) {
        traversal(root);
    }
};

[cyg999]

114采用前序遍历也可以做，不需要返回节点值，只需要一个指针记录当前节点

class Solution {
public:
    TreeNode* cur=nullptr;
    void flatten(TreeNode* root) {
        if(root==nullptr)return;
        cur = root;
        TreeNode* pright = root->right;
        root->right = root->left;
        flatten(root->left);
        root->left = nullptr;
        cur->right = pright;
        flatten(pright);
    }
};

[shiboys]

遍历的方式在返回 void 的情况下，也能实现二叉树拉平

void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        flattenNode(root, queue);
        TreeNode p = queue.poll();
        while (!queue.isEmpty() && p != null) {
            TreeNode rightNode = queue.poll();
            p.left = null;
            p.right = rightNode;
            p = p.right;
        }
    }

void flattenNode(TreeNode node, Queue<TreeNode> queue) {
        if (node == null) {
            return;
        }
        queue.add(node);
        flattenNode(node.left, queue);
        flattenNode(node.right, queue);
    }

[zhaoyangliu]

第二题, 填充右侧节点的, 我觉得抽象成三个节点其实非常的非常规, 比较难想到,似乎让人眼前一亮.但是仔细一想, 里面其实有重复计算的问题. 假设下面还有一层, 8 9 10 11 12 13. 在计算 4 5 的时候, 会把(8,9), (9,10), (10,11)连上, 在计算5, 6的时候,又会尝试(10,11), (11,12), (12,13), 这时候(10,11)就明显重复计算了. 如果我是面试官, 对于这种算法, 我肯定challenge 面试者.

第三题
p = root
while p.right:
p = p.right
p.right = right
这一部分不说多余,但是是明显可以优化掉的. 一个办法就是给flatten弄成带返回值,返回的就是最右边的节点.

这两道题虽然都解出来了,但是都有明显缺陷,虽然这里可能只是说举例思路,但还是不太恰当,希望能多注重算法效率.

[howerlth]

第 114 题「将二叉树展开为链表」

好像遍历也是可以的? 创建一个指针就可以了.

class Solution {
public:
TreeNode* head = new TreeNode(0);
TreeNode* p = head;

// preorder traversal with a pointer concatenating new nodes
void traverse(TreeNode* root) {
    if (root == nullptr)
        return ;
    
    p->right = root;
    p->left = nullptr;
    p = p->right;

    TreeNode* left = root->left;
    TreeNode* right = root->right;

    traverse(left);
    traverse(right);
}

void flatten(TreeNode* root) {
    traverse(root);
}

};

[RayInCode]

@Infinite-Unexpired-Love 提供的解法确实更加合理。

[Infinite-Unexpired-Love]

第二题填充右侧节点，可以直接利用父节点的next指针：
c语言版

typedef struct Node node;
struct Node* connect(struct Node* root) {
	if(root==NULL){
        return NULL;
    }
    //root->next=NULL;  //初始状态下，所有 next 指针都已经被设置为 NULL。
    //不是叶节点
    if(root->left!=NULL){
        root->left->next=root->right;
        //根节点不在三角形的边上
        if(root->next!=NULL){
            root->right->next=root->next->left;
        }
        // else{
        //     root->right->next=NULL;
        // }
    }
    connect(root->left);
    connect(root->right);
    return root;
}

[RayInCode]

你的解法对我很有帮助

[sylviachency]

东哥，请问第三题的时间复杂度要怎么算呢？谢谢

[RayInCode]

借鉴@Infinite-Unexpired-Love 116题的C语言解法，提供一个java版本：

class Solution {
    public Node connect(Node root) {
        if(root == null || root.left == null || root.right == null)
            return root;

        root.left.next = root.right;
        if(root.next != null)
            root.right.next = root.next.left;
        
        connect(root.left);
        connect(root.right);

        return root;
    }
}

[Youarenotblind]

填充节点的右侧指针这一题感觉一眼队列bfs

class Solution 
{
public:
    Node* connect(Node* root) 
    {
        if (!root)
            return root;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                Node *cur = q.front();
                q.pop();
                if (i < sz - 1)
                    cur->next = q.front();
                if (cur->left)
                    q.push(cur->left);
                if (cur->right)
                    q.push(cur->right);
            }
        }
        return root;
    }
};

[qzlu-cyber]

114题：展开二叉树为链表。
根据东哥的“分解思路”的另一种解法

class Solution {
public:
    // 定义：将以 root 为根的二叉树展成单链表，返回单链表的头指针
    TreeNode* func(TreeNode* root) {
        if (root == nullptr) return root;

        // 将左子树展开成单链表
        TreeNode* left = func(root->left);
        // 将右子树展开成单链表
        TreeNode* right = func(root->right);
        // 将 root 的左子树变为右子树
        root->left = nullptr;
        root->right = left;
        // 将 root 原本的右子树挂到新的右子树上
        TreeNode* p = root;
        while (p->right) p = p->right;
        p->right = right;

        return root;
    }

    void flatten(TreeNode* root) {
        func(root);
    }
};

[4ever-marcinho11]

116题感觉用层次遍历也能解：

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int sz = queue.size();
            // 用pre记录同层前一个结点
            Node pre = null;
            for (int i = 0; i < sz; i++) {
                // 常规的层次遍历
                Node current = queue.poll();
                if (current.left != null) {
                    queue.add(current.left);
                }
                if (current.right != null) {
                    queue.add(current.right);
                }

                // 确定next指向
                if (i == 0) {
                    pre = current;
                }
                if (i > 0) {
                    pre.next = current;
                    pre = current;
                    if (i == sz - 1) {
                        current.next = null;
                    }
                }
            }
        }
        return root;
    }
}

[rederyang]

链表展开那题，维护一个last指针，先序在它的后面挂节点（应该属于遍历的思路？）

class Solution {
private:
    TreeNode* last = new TreeNode();
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        last->right = root;
        last = last->right;
        TreeNode *tmp_right = root->right;
        flatten(root->left);
        flatten(tmp_right);
        root->left = nullptr;
    }
};

[gaocan1992]

114 Flatten Binary Tree to Linked List
想的是可以递归函数返回flatten以后list的tail node， 这样可以直接拿到左子树的tail然后和右子树的head连接起来
然后继续flatten右子树再返回右子树的tail，这样不用分别flatten左右子树再寻找左子树的tail和右子树的head连接起来

class Solution {
    public void flatten(TreeNode root) {
        flattenToList(root);
    }

    private TreeNode flattenToList(TreeNode node) {
        if (node == null) return null;
        if (node.left == null && node.right == null) return node;

        TreeNode tail = flattenToList(node.left);
        if (tail == null) {
            return flattenToList(node.right); 
        }

        TreeNode right = node.right;
        node.right = node.left;
        node.left = null;
        tail.right = right;

        return flattenToList(node.right);
    }
}