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

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if(root.left == null && root.right == null)
        {
            return true;
        }
        else if(root.left == null || root.right == null)
        {
            return false;
        }
        Queue<TreeNode> traversal = new LinkedList<>();
        traversal.offer(root.left);
        traversal.offer(root.right);
        while(!traversal.isEmpty())
        {
            TreeNode ptr_left = traversal.poll();
            TreeNode ptr_right = traversal.poll();
            if(ptr_left == null && ptr_right == null)   
            {
                continue;
            }
            else if(ptr_left == null || ptr_right == null || ptr_left.val != ptr_right.val)
            {
                return false;
            }
            traversal.offer(ptr_left.left);
            traversal.offer(ptr_right.right);
            traversal.offer(ptr_left.right);
            traversal.offer(ptr_right.left);
        }
        return true;
    }
}

function isSymmetric(root: TreeNode | null): boolean {
    if (!root) return true;
    return help(root.left, root.right)
};

function help(a: TreeNode, b: TreeNode): boolean {
    if (a === null && b === null) return true;
    if (a === null || b === null) return false;
    return (a.val === b.val) && help(a.left, b.right) && help(a.right, b.left);
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def traverse(node):
            if not node:
                return []
            comps = traverse(node.left) + traverse(node.right)
            ans = []
            for c in comps:
                ans.append(str(node.val) + c)
            return ans if ans else [str(node.val)]
        
        ans = traverse(root)
        s = 0
        for a in ans:
            s += int(a)
        return s

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def traverse(node):
            if not node:
                return []
            comps = traverse(node.left) + traverse(node.right)
            ans = []
            for c in comps:
                ans.append(str(node.val) + c)
            return ans if ans else [str(node.val)]
        
        ans = traverse(root)
        s = 0
        for a in ans:
            s += int(a)
        return s

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.res = 0
        
        self.dfs(root, 0)
        
        return self.res
    
    def dfs(self, node, num):
        if not node:
            return
        
        val = num * 10 + node.val
        if not (node.left or node.right):
            self.res += val
            return
        
        self.dfs(node.left, val)
        self.dfs(node.right, val)

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        res = 0
        
        queue = deque([(root, 0)])
        
        while len(queue) > 0:
            node, val = queue.popleft()
            
            if not node:
                continue
            
            val = val * 10 + node.val
            
            if not (node.left or node.right):
                res += val
                continue
                
            queue.append((node.left, val))
            queue.append((node.right, val))
                
        return res

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sumNumbers(root: TreeNode | null): number {
    const dfs = (node: TreeNode | null, acc: number): number => {
        if (node === null) {
            return 0;
        }

        const currentValue = acc * 10 + node.val;

        if (node.left === null && node.right === null) {
            return currentValue;
        }

        return dfs(node.left, currentValue) + dfs(node.right, currentValue);
    }

    return dfs(root, 0);
};

class Solution {
public:
    int sumNumbers(TreeNode* root, int val = 0) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return val*10 + root->val;
        return sumNumbers(root->left, val*10 + root->val) + sumNumbers(root->right, val*10 + root->val);
    }
};

/**
 * 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 {
    class Node {
        TreeNode node;
        int val;
        public Node(TreeNode node, int val) {
            this.node = node;
            this.val = val;
        }
    }
    public int sumNumbers(TreeNode root) {
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(root, root.val));
        int ans = 0;
        while (!stack.isEmpty()) {
            Node cur = stack.pop();

            if (cur.node.left == null && cur.node.right == null) {
                ans += cur.val;
                continue;
            }

            if (cur.node.left != null) {
                stack.push(new Node(cur.node.left, cur.val*10+ cur.node.left.val));
            }

            if (cur.node.right != null) {
                stack.push(new Node(cur.node.right, cur.val*10 + cur.node.right.val));
            }
        }

        return ans;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    let ans = 0;
    const dfs = (node, s) => {
        s = s * 10 + node.val;
        const children = [node.left, node.right].filter(Boolean);
        if (!children.length) {
            ans += s;
        } else {
            for (const child of children) {
                dfs(child, s);
            }
        }
    };

    dfs(root, 0);

    return ans;
};

class Solution:
 
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        all_sum = 0
        curr_sum = 0
        def dfs(node):
            nonlocal all_sum
            nonlocal curr_sum
            curr_sum = curr_sum * 10 + node.val
            if not node.left and not node.right:
                all_sum += curr_sum

            if node.left:
                dfs(node.left)
            
            if node.right:
                dfs(node.right)

            curr_sum = (curr_sum - node.val)/10

        dfs(root)

        return int(all_sum)

function sumNumbers(root: TreeNode | null): number {
    return dfs(root, 0)
};
function dfs(root: TreeNode, num: number): number {
    if (!root) return 0;
    num = num * 10 + root.val;
    if (!root.left && !root.right)
        return num;
    return dfs(root.left, num) + dfs(root.right, num);
}

/**
 * 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 int sumNumbers(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        HashMap<TreeNode, Integer> currVal = new HashMap<>();
        int ans = 0;
        q.offer(root);
        currVal.put(root, root.val);
        while(q.isEmpty() == false){
            TreeNode current = q.poll();
            int key = currVal.get(current);
            if(current.left != null){
                q.offer(current.left);
                currVal.put(current.left, key * 10 + current.left.val);
            }
            if(current.right != null){
                q.offer(current.right);
                currVal.put(current.right, key * 10 + current.right.val);
            }
            if(current.left == null && current.right == null){
                ans += key;
            }
        }
        return ans;
    }
}

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root: return False
        from collections import deque
        q = deque([root])
        tracks = []
        while q:
            s = len(q)
            temp = []
            for _ in range(s):
                node = q.popleft()
                if node:
                    temp.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
                else:
                    temp.append(None)
            tracks.append(temp)

        for i in range(len(tracks)-1):
            nodes = tracks[i]
            if len(nodes) != 2**i:
                return False
            else:
                has_none = False
                for j in range(len(nodes)):
                    if nodes[j] and has_none:
                        return False
                    elif nodes[j] is None:
                        has_none = True
      
        return True

class Solution:   
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        queue = deque([root])
        
        while len(queue) > 0:
            node = queue.popleft()
            
            if node is None:
                break
                
            queue.append(node.left)
            queue.append(node.right)
        
        for node in queue:
            if node is not None:
                return False
            
        return True

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        stack = [(root, 0)]
        nulls = set()
        levelCount = defaultdict(int)
        
        while len(stack) > 0:
            node, level = stack.pop()
            
            if node is None:
                if level not in nulls:
                    nulls.add(level)
                    
                continue
            
            levelCount[level] += 1
            
            if level in nulls:
                return False
            
            stack.append((node.right, level + 1))
            stack.append((node.left, level + 1))
        
        height = max(levelCount)
        
        # Exclude the last level
        for level in range(0, height):
            if levelCount[level] < 2 ** level:
                return False
    
        return True

function isCompleteTree(root: TreeNode | null): boolean {
    let check = false;
    let queue = [root];

    while (queue.length) {
        const sub: TreeNode[] = [];
        for (let nextNode of queue) {
            if (!nextNode) check = true;
            else {
                if (check) return false;
                sub.push(nextNode.left);
                sub.push(nextNode.right);
            }
        }
        queue = sub;
    }
    return true
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function(root) {
    let height, last;

    const dfs = (node, h) => {
        if (node) {
            return dfs(node.left, h + 1) && dfs(node.right, h + 1);
        }

        if (!height) {
            height = last = h;
            return true;
        }

        if (h === height-1 || last === height && h === height) {
            last = h;
            return true;
        }

        return false;

    }

    return dfs(root, 0);
};

function isCompleteTree(root: TreeNode | null): boolean {
    let isNullFound = false;
    let queue: TreeNode[] = [root];

    while(queue.length) {
        const temp: TreeNode[] = [];

        for (const next of queue) {
            if (next === null) {
                isNullFound = true;
            } else {
                if (isNullFound) {
                    return false;
                }

                temp.push(next.left, next.right);
            }
        }

        queue = temp;
    }

    return true;
};

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean terminal = false;
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            if (cur == null) continue;
            if (cur.left == null && cur.right != null) return false;          
            if (terminal) {
                if (cur.left != null || cur.right != null) return false;
            }
            if (cur.left == null || cur.right == null) terminal = true;
            q.add(cur.left);
            q.add(cur.right);
        }

        return true;
    }
}

class Solution {
  int lastH = -1;
  int firstH = -1;
  public boolean isCompleteTree(TreeNode root) {
    return dfs(root, 0);
  }

  boolean dfs(TreeNode node, int h) {
    if (node == null) {
      boolean ans = (lastH == -1 || lastH == h+1 || lastH == h)
        && (firstH == -1 || firstH == h+1 || firstH == h);
      lastH = h;
      firstH = firstH == -1 ? h : firstH;
      return ans;
    }
    boolean ans = dfs(node.left, h+1);
    if (!ans) return ans;
    return dfs(node.right, h+1);
  }

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def build(left, right):
            nonlocal idx
            if left > right: return
            root = TreeNode(postorder[idx])
            index = 0
            for i in range(left,right+1):
                if inorder[i] == postorder[idx]:
                    index = i
                    break
            idx -= 1
            root.right = build(index+1, right)
            root.left = build(left, index-1)
            return root
        idx = len(postorder) - 1
        return build(0, len(inorder)-1)