thảo luận Leetcode mỗi ngày

use std::rc::Rc;
use std::cell::RefCell;

type Node = Rc<RefCell<TreeNode>>;

impl Solution {
    pub fn postorder_traversal(root: Option<Node>) -> Vec<i32> {
        let mut stack = vec![];
        let mut result = vec![];

        let (left, right, done) = (0, 1, 2);
        stack.push((root, left));

        while let Some((node, state)) = stack.pop() {
            match state {
                0 => {
                    match node {
                        Some(node) => {
                            let left = node.borrow().left.clone();

                            stack.push((Some(node), 1));
                            stack.push((left, 0));
                        },
                        None => ()
                    }
                },
                1 => {
                    match node {
                        Some(node) => {
                            let right = node.borrow().right.clone();

                            stack.push((Some(node), 2));
                            stack.push((right, 0));
                        },
                        None => ()
                    }
                },
                2 => {
                    match node {
                        Some(node) => result.push(node.borrow().val),
                        None => ()
                    }
                },
                _ => ()
            }
        }

        result
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> tree = new LinkedList<Integer>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return tree;
        TreeNode curr = root;
        while(curr!= null || !stack.isEmpty()){
            while(curr!= null){
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode a = stack.peek();
            if (a.right == null) {
                TreeNode b = stack.pop();
                tree.add(b.val);
            } else {
                curr = a.right;
                a.right = null;
            }
        }
        return tree;
    }
}

var postorderTraversal = function(root) {
    const ans = [];
    if (!root) return ans;

    const stack = [root];
    while (stack.length) {
        const node = stack.pop();
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
        ans.push(node.val);
    }
    return ans.reverse();
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postorderTraversal(list, root);
        return list;
    }

    private void postorderTraversal(List<Integer> list, TreeNode head) {
        if (head == null) return;
        postorderTraversal(list, head.left);
        postorderTraversal(list, head.right);
        list.add(head.val);
    }
}

def postorder_traversal(root)
    @result = []
    dfs(root)
    @result
end

def dfs root
    return if root.nil?
    dfs(root.left) if root.left
    dfs(root.right) if root.right
    @result << root.val
end

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(root):
            if not root:
                return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)

        res = []
        postorder(root)
        return res

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(node):
            if not node:
                return
            yield from postorder(node.left)
            yield from postorder(node.right)
            yield node.val

        return list(postorder(root))

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def traverse(node):
            if node is not None:
                traverse(node.left)
                traverse(node.right)
                result.append(node.val)

        traverse(root)

        return result

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        self.result = []

        def traverse(node):
            if node is None:
                return
            
            for child in node.children:
                traverse(child)
            self.result.append(node.val)

        traverse(root)
        return self.result

/**
 * Definition for node.
 * class _Node {
 *     val: number
 *     children: _Node[]
 *     constructor(val?: number) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.children = []
 *     }
 * }
 */

function postorder(root: _Node | null): number[] {
    const res: number[] = [];
    const stack = [root];
    while(stack.length) {
        const node = stack.pop();
        if (!node) continue;
        res.unshift(node.val);
        for (const child of node.children) stack.push(child)
    }
    return res;
};

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        postorderTraversal(list, root);
        return list;
    }

    private void postorderTraversal(List<Integer> list, Node node) {
        if (node == null) return;
        for (Node children : node.children) {
            postorderTraversal(list, children);
        }
        list.add(node.val);
    }
}

var postorder = function(root) {
    var dfs = function (node) {
        if (!node) return;
        for (const child of node.children) {
            dfs(child);
        }
        res.push(node.val);
    }

    let res = [];
    dfs(root);
    return res;
};

class Solution {
    /**
     * @param Node $root
     * @return integer[]
     */
    function postorder($root) {
        if (!$root) return [];

        $stack = [$root];
        $ans = [];
        while (count($stack)) {
            $node = array_pop($stack);
            if (!count($node->children)) {
                $ans[] = $node->val;
                continue;
            }

            $stack[] = $node;    
            $children = $node->children;
            for ($i=count($children)-1; $i>=0; $i--) {
                if (!$children[$i]) continue;
                $stack[] = $children[$i];
            }
            $node->children = [];
        }

        return $ans;
    }
}

class Solution {
    func postorder(_ root: Node?) -> [Int] {
        guard let root else { return [] }
        var result:[Int] = []
        func dfs(_ tree: Node) {
            tree.children.forEach{ dfs($0) }
            result.append(tree.val)
        }
        dfs(root)
        return result
    }
}