cloud域名注册网站,目前建设网站,竹子林附近网站建设,朝阳专业网站建设Problem: 1022. 从根到叶的二进制数之和 文章目录 题目描述思路复杂度Code 题目描述 思路
遍历思想(利用二叉树的先序遍历) 1.在先序遍历的过程中#xff0c;用一个变量path记录并更新其经过的路径上的值#xff0c;当遇到根节点时再将其加到结果值res上#xff1b; 2.该题… Problem: 1022. 从根到叶的二进制数之和 文章目录 题目描述思路复杂度Code 题目描述 思路
遍历思想(利用二叉树的先序遍历) 1.在先序遍历的过程中用一个变量path记录并更新其经过的路径上的值当遇到根节点时再将其加到结果值res上 2.该题中要注意数值的二进制操作该题中path path 1 | root.val;即通过不断地左移由于题目所说数值均为32位整数并再与当前节点值相或来更新path记录地值 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为二叉树的节点个数 空间复杂度: O ( h ) O(h) O(h)其中 h h h为二叉树的高度 Code
/*** 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 sumRootToLeaf(TreeNode root) {traverse(root);return res;}int path 0;int res 0;private void traverse(TreeNode root) {if (root null) {return;}// Leaf rootif (root.left null root.right null) {// Add the value on the path to the resres path 1 | root.val;return;}// Change the value of pathpath path 1 | root.val;traverse(root.left);traverse(root.right);path path 1;}
}
