Skip to content

Latest commit

 

History

History
445 lines (384 loc) · 12.7 KB

0116.填充每个节点的下一个右侧节点指针.md

File metadata and controls

445 lines (384 loc) · 12.7 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

116. 填充每个节点的下一个右侧节点指针

力扣题目链接

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

思路

注意题目提示内容，：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

基本上就是要求使用递归了，迭代的方式一定会用到栈或者队列。

递归

一想用递归怎么做呢，虽然层序遍历是最直观的，但是递归的方式确实不好想。

如图，假如当前操作的节点是cur：

最关键的点是可以通过上一层递归 搭出来的线，进行本次搭线。

图中cur节点为元素4，那么搭线的逻辑代码：（注意注释中操作1和操作2和图中的对应关系）

if (cur->left) cur->left->next = cur->right; // 操作1
if (cur->right) {
    if (cur->next) cur->right->next = cur->next->left; // 操作2
    else cur->right->next = NULL;
}

理解到这里，使用前序遍历，那么不难写出如下代码：

class Solution {
private:
    void traversal(Node* cur) {
        if (cur == NULL) return;
                                // 中
        if (cur->left) cur->left->next = cur->right; // 操作1
        if (cur->right) {
            if (cur->next) cur->right->next = cur->next->left; // 操作2
            else cur->right->next = NULL;
        }
        traversal(cur->left);   // 左
        traversal(cur->right);  // 右
    }
public:
    Node* connect(Node* root) {
        traversal(root);
        return root;
    }
};

迭代（层序遍历）

本题使用层序遍历是最为直观的，如果对层序遍历不了解，看这篇：二叉树：层序遍历登场！。

遍历每一行的时候，如果不是最后一个Node，则指向下一个Node；如果是最后一个Node，则指向nullptr。

代码如下：

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != nullptr) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; ++i) {
                Node* node = que.front();
                que.pop();
                if (i != size - 1) {
                    node->next = que.front(); //如果不是最后一个Node 则指向下一个Node
                } else node->next = nullptr;  //如果是最后一个Node 则指向nullptr
                if (node->left != nullptr) que.push(node->left);
                if (node->right != nullptr) que.push(node->right);
            }
        }
        return root;
    }
};

其他语言版本

Java

// 递归法
class Solution {
    public void traversal(Node cur) {
        if (cur == null) return;
        if (cur.left != null) cur.left.next = cur.right; // 操作1
        if (cur.right != null) {
            if(cur.next != null) cur.right.next = cur.next.left; //操作2
            else cur.right.next = null;
        }
        traversal(cur.left);  // 左
        traversal(cur.right); //右
    }
    public Node connect(Node root) {
        traversal(root);
        return root;
    }
}

// 迭代法
class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        Queue<Node> que = new LinkedList<Node>();
        que.offer(root);
        Node nodePre = null;
        Node node = null;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i=0; i<size; i++) { // 开始每一层的遍历
                if (i == 0) {
                    nodePre = que.peek(); // 记录一层的头结点
                    que.poll();
                    node = nodePre;
                } else {
                    node = que.peek();
                    que.poll();
                    nodePre.next = node; // 本层前一个节点next指向本节点
                    nodePre = nodePre.next; 
                }
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            nodePre.next = null; // 本层最后一个节点指向null
        }
        return root;
    }
}

Python

# 递归法
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        def traversal(cur: 'Node') -> 'Node':
            if not cur: return []
            if cur.left: cur.left.next = cur.right # 操作1
            if cur.right:
                if cur.next:
                    cur.right.next = cur.next.left # 操作2
                else:
                    cur.right.next = None
            traversal(cur.left) # 左
            traversal(cur.right) # 右
        traversal(root)
        return root

# 迭代法
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return 
        res = []
        queue = [root]
        while queue:
            size = len(queue)
            for i in range(size): # 开始每一层的遍历
                if i==0: 
                    nodePre = queue.pop(0) # 记录一层的头结点
                    node = nodePre
                else:
                    node = queue.pop(0)
                    nodePre.next = node # 本层前一个节点next指向本节点
                    nodePre = nodePre.next
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            nodePre.next = None # 本层最后一个节点指向None
        return root

Go

// 迭代法
func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    stack := make([]*Node, 0)
    stack = append(stack, root)
    for len(stack) > 0 {
        n := len(stack) // 记录当前层节点个数
        for i := 0; i < n; i++ {
            node := stack[0] // 依次弹出节点
            stack = stack[1:]
            if i == n - 1 { // 如果是这层最右的节点，next指向nil
                node.Next = nil 
            } else {
                node.Next = stack[0] // 如果不是最右的节点，next指向右边的节点
            }
            if node.Left != nil { // 如果存在左子节点，放入栈中
                stack = append(stack, node.Left)
            }
            if node.Right != nil { // 如果存在右子节点，放入栈中
                stack = append(stack, node.Right)
            }
        }
    }
    return root
}

// 常量级额外空间，使用next
func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    for cur := root; cur.Left != nil; cur = cur.Left { // 遍历每层最左边的节点
        for node := cur; node != nil; node = node.Next { // 当前层从左到右遍历
            node.Left.Next = node.Right // 左子节点next指向右子节点
            if node.Next != nil { //如果node next有值，右子节点指向next节点的左子节点
                node.Right.Next = node.Next.Left
            }
            
        }
    }   
    return root
}

JavaScript

const connect = root => {
    if (!root) return root;
    // 根节点入队
    const Q = [root];
    while (Q.length) {
        const len = Q.length;
        // 遍历这一层的所有节点
        for (let i = 0; i < len; i++) {
            // 队头出队
            const node = Q.shift();
            // 连接
            if (i < len - 1) {
                // 新的队头是node的右边元素
                node.next = Q[0];
            }
            // 队头左节点有值，放入队列
            node.left && Q.push(node.left);
            // 队头右节点有值，放入队列
            node.right && Q.push(node.right);
        }
    }
    return root;
};

TypeScript

（注：命名空间‘Node’与typescript中内置类型冲突，这里改成了‘NodePro’）

递归法：

class NodePro {
    val: number
    left: NodePro | null
    right: NodePro | null
    next: NodePro | null
    constructor(val?: number, left?: NodePro, right?: NodePro, next?: NodePro) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
        this.next = (next === undefined ? null : next)
    }
}

function connect(root: NodePro | null): NodePro | null {
    if (root === null) return null;
    root.next = null;
    recur(root);
    return root;
};
function recur(node: NodePro): void {
    if (node.left === null || node.right === null) return;
    node.left.next = node.right;
    node.right.next = node.next && node.next.left;
    recur(node.left);
    recur(node.right);
}

迭代法：

class NodePro {
    val: number
    left: NodePro | null
    right: NodePro | null
    next: NodePro | null
    constructor(val?: number, left?: NodePro, right?: NodePro, next?: NodePro) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
        this.next = (next === undefined ? null : next)
    }
}

function connect(root: NodePro | null): NodePro | null {
    if (root === null) return null;
    const queue: NodePro[] = [];
    queue.push(root);
    while (queue.length > 0) {
        for (let i = 0, length = queue.length; i < length; i++) {
            const curNode: NodePro = queue.shift()!;
            if (i === length - 1) {
                curNode.next = null;
            } else {
                curNode.next = queue[0];
            }
            if (curNode.left !== null) queue.push(curNode.left);
            if (curNode.right !== null) queue.push(curNode.right);
        }
    }
    return root;
};

//递归
public class Solution {
    public Node Connect(Node root) {
        if (root == null) {
            return null;
        }
        
        ConnectNodes(root.left, root.right);
        
        return root;
    }

    private void ConnectNodes(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return;
        }

        // 将左子节点的 next 指向右子节点
        node1.next = node2;

        // 递归连接当前节点的左右子节点
        ConnectNodes(node1.left, node1.right);
        ConnectNodes(node2.left, node2.right);

        // 连接跨越父节点的两个子树
        ConnectNodes(node1.right, node2.left);
    }
}


// 迭代
public class Solution
{
    public Node Connect(Node root)
    {
        Queue<Node> que = new Queue<Node>();

        if (root != null)
        {
            que.Enqueue(root);
        }

        while (que.Count > 0)
        {

            var queSize = que.Count;
            for (int i = 0; i < queSize; i++)
            {
                var cur = que.Dequeue();

                // 当这个节点不是这一层的最后的节点
                if (i != queSize - 1)
                {
                    // 当前节点指向下一个节点
                    cur.next = que.Peek();
                }
                // 否则指向空
                else
                {
                    cur.next = null;
                }

                if (cur.left != null)
                {
                    que.Enqueue(cur.left);
                }
                if (cur.right != null)
                {
                    que.Enqueue(cur.right);
                }
            }
        }

        return root;
    }
}