LeetCode（Tree)2236. Root Equals Sum of Children

喜欢ヅ旅行 2023-09-26 20:37 84阅读 0赞

# 1.问题 #

You are given the root of a binary tree that consists of exactly 3 nodes: the root, its left child, and its right child.

Return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.

Example 1:  
![在这里插入图片描述][f7c0b2f426c442a0aad5cd9c5234d1e4.png]

> Input: root = \[10,4,6\]  
> Output: true  
> Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively.  
> 10 is equal to 4 + 6, so we return true.

Example 2:

![在这里插入图片描述][ac848f86739e43939bbd8d1125936bb4.png]

> Input: root = \[5,3,1\]  
> Output: false  
> Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively.  
> 5 is not equal to 3 + 1, so we return false.

Constraints:

*  The tree consists only of the root, its left child, and its right child.
 *  \-100 <= Node.val <= 100

# 2. 解题思路 #

## 方法1： ##

> 1.计算根节点的值  
> 2.如果根节点的值等于左子树的值加右子树的值，则返回true，否则返回false

## 方法2： ##

> 递归方法：  
> 该解法使用递归算法，遍历整棵树  
> 1.递归计算每个节点的左右子树的节点值之和，然后判断当前节点的节点值是否等于左右子树的节点值之和  
> 2.如果满足条件，继续递归检查左右子树，直到遍历完整棵树。  
> 3.如果遍历过程中有任何一个节点不满足条件，则直接返回 false，表示该树不满足条件。

## 方法3： ##

> 迭代方法  
> 1.使用了一个栈来进行迭代，栈中存放的是节点。  
> 2.首先将根节点压入栈中，然后在每一次迭代中弹出一个节点，并将其左右子节点压入栈中。  
> 3.计算当前节点左右子节点的值之和，如果不等于当前节点的值，那么就返回 false。  
> 4.最终如果栈中的所有节点都被遍历完了，那么就返回 true。

# 3. 代码 #

## 代码1： ##

/**
     * 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 checkTree(TreeNode root) {
        
            // 计算根节点的值
            int sum = root.val;
            // 如果根节点的值等于左子树的值加右子树的值，则返回true，否则返回false
            if (sum == root.left.val + root.right.val) {
        
                return true;
            }
            return false;
        }
    }

## 代码2： ##

class Solution {
        
     public boolean checkTree(TreeNode root) {
        
            if (root == null) {
         // 如果根节点为空，则满足条件
                return true;
            }
            if (root.left == null && root.right == null) {
         // 如果当前节点为叶子节点，则满足条件
                return true;
            }
            int leftSum = sum(root.left); // 计算左子树的节点值之和
            int rightSum = sum(root.right); // 计算右子树的节点值之和
            return root.val == leftSum + rightSum && checkTree(root.left) && checkTree(root.right); // 递归检查左右子树
        }
    
        // 计算以 root 为根节点的子树节点值之和
        private int sum(TreeNode root) {
        
            if (root == null) {
         // 如果根节点为空，则返回 0
                return 0;
            }
            return root.val + sum(root.left) + sum(root.right); // 递归计算左右子树的节点值之和
        }
    }

## 代码3： ##

由于此题与LeetCode上的题目编号不一致，以下是针对描述进行的代码注释：
    
    // 题目描述：判断一棵二叉树的根节点的值是否等于其子节点值之和
    class Solution {
        
    	public boolean checkTree(TreeNode root) {
        
    		// 如果根节点为空，则返回false
    		if (root == null) {
        
    		return false;
    		}
    		// 定义一个栈，用于迭代二叉树
    		Stack<TreeNode> stack = new Stack<>();
    		// 将根节点入栈
    		stack.push(root);
    		// 迭代栈中所有节点
    		while (!stack.isEmpty()) {
        
    			// 弹出栈顶节点
    			TreeNode node = stack.pop();
    			// 如果该节点的左子节点不为空，则将其入栈
    			if (node.left != null) {
        
    			stack.push(node.left);
    			}
    			// 如果该节点的右子节点不为空，则将其入栈
    			if (node.right != null) {
        
    			stack.push(node.right);
    			}
    			// 如果该节点的值不等于其左子节点值与右子节点值之和，则返回false
    			if (node.val != (node.left != null ? node.left.val : 0) + (node.right != null ? node.right.val : 0)) {
        
    			return false;
    			}
    		}
    		// 遍历完成后，如果没有返回false，则返回true
    		return true;
    	}
    }

[f7c0b2f426c442a0aad5cd9c5234d1e4.png]: https://img-blog.csdnimg.cn/f7c0b2f426c442a0aad5cd9c5234d1e4.png
[ac848f86739e43939bbd8d1125936bb4.png]: https://img-blog.csdnimg.cn/ac848f86739e43939bbd8d1125936bb4.png