144. Binary Tree Preorder Traversal

leetcode easy

#csharp#easy#leetcode#stack#tree#two-pointers

Task

Дан корень бинарного дерева, верните предварительный обход значений его узлов.

Пример:

Input: root = [1,null,2,3]

Output: [1,2,3]

C# solution

matched/original

public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        IList<int> res = new List<int>();
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        while (stack.Count != 0) {
            TreeNode curr = stack.Pop();
            res.Add(curr.val);
            if (curr.right != null)
                stack.Push(curr.right);
            if (curr.left != null)
                stack.Push(curr.left);
        }
        return res;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> PreorderTraversal(TreeNode root) {
        vector<int> res = new List<int>();
        if (root == null)
            return res;
        stack<TreeNode> stack = new stack<TreeNode>();
        stack.push(root);
        while (stack.size() != 0) {
            TreeNode curr = stack.pop();
            res.push_back(curr.val);
            if (curr.right != null)
                stack.push(curr.right);
            if (curr.left != null)
                stack.push(curr.left);
        }
        return res;
    }
}

Java solution

matched/original

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollLast();
            output.add(node.val);
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                stack.add(node.left);
            }
        }
        return output;
    }
}

JavaScript solution

matched/original

var preorderTraversal = function (root) {
    if (!root) {
        return [];
    }

    const stack = [root];
    const output = [];

    while (stack.length != 0) {
        root = stack.pop();
        if (root) {
            output.push(root.val);
            if (root.right) {
                stack.push(root.right);
            }
            if (root.left) {
                stack.push(root.left);
            }
        }
    }

    return output;
};

Python solution

matched/original

class Solution(object):
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        stack, output = [
            root,
        ], []

        while stack:
            root = stack.pop()
            if root is not None:
                output.append(root.val)
                if root.right is not None:
                    stack.append(root.right)
                if root.left is not None:
                    stack.append(root.left)

        return output

Go solution

matched/original

func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    stack := []*TreeNode{root}

    output := []int{}

    for len(stack) > 0 {
        length := len(stack)
        root = stack[length-1]
        stack = stack[:length-1]

        if root != nil {
            output = append(output, root.Val)
        }

        if root.Right != nil {
            stack = append(stack, root.Right)
        }

        if root.Left != nil {
            stack = append(stack, root.Left)
        }
    }

    return output
}

Explanation

Algorithm

1️⃣

Определение структуры узла дерева:

Определите класс TreeNode, который будет использоваться в реализации. Каждый узел TreeNode содержит значение и ссылки на левого и правого потомков.

2️⃣

Инициализация процесса обхода:

Начните обход с корневого узла дерева. Используйте стек для хранения узлов дерева, которые нужно обойти, начиная с корня.

3️⃣

Итеративный обход дерева:

На каждой итерации извлекайте текущий узел из стека и добавляйте его значение в выходной список.

Сначала добавьте в стек правого потомка (если он существует), затем левого потомка (если он существует). Это гарантирует, что узлы будут обрабатываться в порядке слева направо, так как стек работает по принципу LIFO (последний пришел - первый ушел).

Повторяйте процесс, пока стек не опустеет, что означает завершение обхода всех узлов.

😎