字节面试：实现函数接受任意二叉树，求二叉树所有根到叶子路径组成的数字之和

柔情只为你懂 2023-07-19 04:57 6阅读 0赞

**题目：**  
实现函数接受任意二叉树，求二叉树所有根到叶子路径组成的数字之和。  
解决办法：使用递归方法层层遍历相加

// 1
    // 2 3
    // 4 5 6 7
    //结果：(1+2)+(1+3)+(2+4)+(2+5)+(3+6)+(3+7) // 39

// 实现函数接受任意二叉树，求二叉树所有根到叶子路径组成的数字之和。
    class TreeNode { 
      value: number
      left?: TreeNode
      right?: TreeNode
    }
    
    function getPathSum(root) { 
      // your code
    }
    
    // 例子，一层二叉树如下定义，路径包括 1 -> 2， 1 -> 3
    const node = new TreeNode();
    node.value = 1;
    node.left = new TreeNode();
    node.left.value = 2;
    node.right = new TreeNode();
    node.right.value = 3;
    
    getPathSum(node) // return 7 =（1+2）+（1+3）

--------------------

解答：

class TreeNode { }
    const node = new TreeNode();
    node.value = 1;
    node.left = new TreeNode();
    node.left.value = 2;
    node.right = new TreeNode();
    node.right.value = 3;
    // 下面数据便于测试使用 结果：39
    node.left.left = new TreeNode();
    node.left.left.value = 4
    node.left.right = new TreeNode();
    node.left.right.value = 5
    node.right.left = new TreeNode();
    node.right.left.value = 6
    node.right.right = new TreeNode();
    node.right.right.value = 7
    
    
    function getPathSum(node) { 
    	let num = 0;
    
    	function addNum(node) { 
    		if(node.left) { 
    			num += (node.value + node.left.value)
    			if(node.left.left) { 
    				addNum(node.left)
    			} else if(node.left.right) { 
    				addNum(node.left)
    			}
    		}
    		if(node.right) { 
    			num += (node.value + node.right.value)
    			if(node.right.left) { 
    				addNum(node.right)
    			} else if(node.right.right) { 
    				addNum(node.right)
    			}
    		}
    	}
    
    	addNum(node)
    	console.log(num)	// 39
    }
    getPathSum(node)