513.找树左下角的值 文章:16. 找树左下角的值
题目:513. 找树左下角的值
【思路】
用层序遍历,循环遍历获得每一层的第0位,最后赋值的即最后一层(左下角)的值 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int findBottomLeftValue (TreeNode root) { Queue<TreeNode> queue = new LinkedList <>(); queue.add(root); int res = 0 ; while (!queue.isEmpty()){ int len = queue.size(); for (int i = 0 ;i<len;i++){ TreeNode node = queue.poll(); if (i==0 )res = node.val; if (node.left!=null )queue.add(node.left); if (node.right != null )queue.add(node.right); } } return res; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 func findBottomLeftValue (root *TreeNode) int { res :=0 curLevel := []*TreeNode{root} for len (curLevel)>0 { nextLevel :=[]*TreeNode{} for index,node := range curLevel{ if index == 0 { res = node.Val } if node.Left!=nil { nextLevel = append (nextLevel,node.Left) } if node.Right!=nil { nextLevel = append (nextLevel,node.Right) } } curLevel = nextLevel } return res }
112.路径总和 文章:17. 路径总和
题目:112. 路径总和
【思路】
使用递归的方法,将targetSum
转化为每层减去相应的node.val
,这样只需要判断最后targetSum
是否等于当前层的node.val
即可
1 2 3 4 5 6 7 8 9 class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root ==null)return false; if(root.left == null && root.right==null && targetSum==root.val){ return true; } return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val); } }
Go实现
未省略版:每层的val已经被提前减去了,最后只需要判断==0即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 func hasPathSum (root *TreeNode, targetSum int ) bool { var traversal func (node *TreeNode ,res int ) bool traversal = func (node *TreeNode,count int ) bool { if node ==nil { return false } if node.Left == nil &&node.Right ==nil &&count ==0 { return true } if node.Left==nil &&node.Right==nil { return false } if node.Left!=nil { if traversal(node.Left,count-node.Left.Val){ return true } } if node.Right!=nil { if traversal(node.Right,count-node.Right.Val){ return true } } return false } return traversal(root,targetSum) }
省略版:当最后一层(叶子节点)的值==targetSum
,即说明这条路径上所有节点值相加等于目标和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 func hasPathSum (root *TreeNode, targetSum int ) bool { if root == nil { return false } if (root.Left==nil &&root.Right == nil &&targetSum == root.Val){ return true } return hasPathSum(root.Left,targetSum -root.Val) || hasPathSum(root.Right,targetSum-root.Val) }
113.路径总和II 文章:17. 路径总和
题目:113. 路径总和 II
【思路】
113.路径总和II需要遍历整个树,找到所有路径,所以递归函数不要返回值
Java实现
回溯算法需要注意递归之后需要去除当前节点的值,不然会把二叉树内所有的路径都遍历一遍。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> res = new ArrayList<>(); if(root==null)return res; List<Integer>path = new LinkedList<>(); preorderdfs(root,targetSum,res,path); return res; } public void preorderdfs(TreeNode node,int targetSum ,List<List<Integer>>res,List<Integer>path){ path.add(node.val); if(node.left==null && node.right == null){ if(targetSum - node.val == 0){ res.add(new ArrayList<>(path)); } return; } if(node.left!=null){ preorderdfs(node.left,targetSum-node.val,res,path); path.remove(path.size()-1); //回溯 } if(node.right!=null){ preorderdfs(node.right,targetSum-node.val,res,path); path.remove(path.size()-1); } } }
Go实现
if node.Left == nil && node.Right == nil && targetSum == 0{ //不能直接将currPath放到res里面,因为currPath是共享的,指针指向的是同一个地址,每次遍历子树时都会被修改 copyPath := make([]int,len(*currPath)) for i,path := range *currPath{ copyPath[i]=path } *res = append(*res,copyPath) }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 func pathSum (root *TreeNode, targetSum int ) [][]int { res := make ([][]int ,0 ) traverse(root,&res,new ([]int ),targetSum) return res } func traverse (node *TreeNode,res *[][]int ,currPath *[]int ,targetSum int ) { if node == nil { return } targetSum -= node.Val *currPath = append (*currPath,node.Val) if node.Left == nil && node.Right == nil && targetSum == 0 { copyPath := make ([]int ,len (*currPath)) for i,path := range *currPath{ copyPath[i]=path } *res = append (*res,copyPath) } traverse(node.Left,res,currPath,targetSum) traverse(node.Right,res,currPath,targetSum) *currPath = (*currPath)[:len (*currPath)-1 ] }
106.从中序与后序遍历序列构造二叉树 文章:18. 从中序与后序遍历序列构造二叉树
题目:106. 从中序与后序遍历序列构造二叉树
视频:坑很多!来看看你掉过几次坑 | LeetCode:106.从中序与后序遍历序列构造二叉树_哔哩哔哩_bilibili
【思路】
第一步:如果数组大小为0的话,说明是空节点。 第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。 第三步:找到后序遍历最后一个元素在中序数组的位置,作为切割点 第四步:切割中序数组,切成中序左数组和中序右数组(一定是先切中序数组) 第五步:切割后序数组 切好后序左数组和后序右数组 第六步:递归处理左区间和右区间
切割中序数组和后序数组最关键的是要确定好切割的四个区间,坚持循环不变量原则。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { Map<Integer,Integer>map; public TreeNode buildTree (int [] inorder, int [] postorder) { map =new HashMap <>(); for (int i = 0 ;i < inorder.length;i++){ map.put(inorder[i],i); } return findNode(inorder,0 ,inorder.length,postorder,0 ,postorder.length); } public TreeNode findNode (int [] inorder,int inBegin,int inEnd,int [] postorder,int poBegin,int poEnd) { if (inBegin>= inEnd || poBegin>= poEnd){ return null ; } int rootIndex=map.get(postorder[poEnd-1 ]); TreeNode root = new TreeNode (inorder[rootIndex]); int lenOfLeft = rootIndex-inBegin; root.left=findNode(inorder,inBegin,rootIndex,postorder,poBegin,poBegin+lenOfLeft); root.right = findNode(inorder,rootIndex+1 ,inEnd,postorder,poBegin+lenOfLeft,poEnd-1 ); return root; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 var ( hash map [int ]int ) func buildTree (inorder []int , postorder []int ) *TreeNode { hash = make (map [int ]int ) for i, v := range inorder{ hash[v] = i } root := rebuild(inorder,postorder,len (postorder)-1 ,0 ,len (inorder)-1 ) return root } func rebuild (inorder []int ,postorder []int ,rootIdx int ,l,r int ) { if l > r { return nil } if l == r{ return &TreeNode{Val: inorder[l]} } rootV := postorder[rootIdx] index := hash[rootV] root := &TreeNode{Val: rootV} root.Left = rebuild(inorder,postorder,rootIdx-(r - index) -1 ,l,index-1 ) rot.Right = rebuild(inorder,postorder,rootIdx-1 ,index+1 ,r) }
105.从前序与中序遍历序列构造二叉树 文章:18. 从中序与后序遍历序列构造二叉树
题目:105. 从前序与中序遍历序列构造二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { Map<Integer,Integer>map; public TreeNode buildTree (int [] preorder, int [] inorder) { map = new HashMap <>(); for (int i = 0 ;i < inorder.length;i++){ map.put(inorder[i],i); } return findNode(preorder,0 ,preorder.length,inorder,0 ,inorder.length); } public TreeNode findNode (int [] preorder,int preStart,int preEnd,int []inorder,int inStart,int inEnd) { if (preStart >= preEnd || inStart >= inEnd){ return null ; } int rootIndex = map.get(preorder[preStart]); TreeNode root = new TreeNode (inorder[rootIndex]); int lenOfLeft = rootIndex - inStart; root.left = findNode(preorder,preStart+1 ,preStart+lenOfLeft+1 ,inorder,inStart,rootIndex); root.right = findNode(preorder,preStart+lenOfLeft+1 ,preEnd,inorder,rootIndex+1 ,inEnd); return root; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 var ( hash map [int ]int ) func buildTree (preorder []int , inorder []int ) *TreeNode { hash = make (map [int ]int ,len (inorder)) for i,v :=range inorder{ hash[v] = i } root := traversal(preorder,inorder,0 ,0 ,len (inorder)-1 ) return root } func traversal (preorder []int ,inorder []int ,root int ,l,r int ) *TreeNode{ if l > r { return nil } rootVal := preorder[root] index := hash[rootVal] node := &TreeNode {Val: rootVal} node.Left=traversal(preorder,inorder,root+1 ,l,index-1 ) node.Right=traversal(preorder,inorder,root+(index-l)+1 ,index+1 ,r) return node }
【算法总结】
找树左下角的值:采用层次遍历即可
路径总和&II:需要分清楚什么时候递归需要/不需要返回值,遍历整个二叉树就不用返回值。
中序和后序遍历序列构造二叉树&&前序和中序序列构造二叉树:这两题还不是很理解rootIdx
的具体计算,还需要复盘一下。