福州网站建设fjfzwl,推广网站的网址和网鱼相匹配,广东广州网点快速网站建设,杭州微信网站开发513. 找树左下角的值
题目#xff1a;给定一个二叉树的 根节点 root#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。
示例 1: 输入: root [2,1,3] 输出: 1 思路一#xff1a;层序遍历#xff0c;最后一层的第一个元素#xff0c;即…513. 找树左下角的值
题目给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。
示例 1: 输入: root [2,1,3] 输出: 1 思路一层序遍历最后一层的第一个元素即是树左下角的值。 思路二通过递归深度优先遍历原则因为本题没有 中间节点的处理逻辑所以使用前、中、后序遍历都可以保证优先左边搜索然后记录深度最大的叶子节点此时就是树的最后一行最左边的值 思路一层序遍历 C#代码
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) {* this.val val;* this.left left;* this.right right;* }* }*/
public class Solution {public int FindBottomLeftValue(TreeNode root) {var result 0;if(root null) return result;var queue new QueueTreeNode();queue.Enqueue(root);while(queue.Any()){int len queue.Count;var itemList new Queueint();while(len0){var temp queue.Dequeue();itemList.Enqueue(temp.val);if(temp.left!null) queue.Enqueue(temp.left);if(temp.right!null) queue.Enqueue(temp.right);len--;}result itemList.Dequeue();}return result;}
}思路二递归 C#代码
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) {* this.val val;* this.left left;* this.right right;* }* }*/
public class Solution {//结果值int result 0;//最大深度int maxDepth -1;public int FindBottomLeftValue(TreeNode root) {Traversal(root,1);return result;}// 1. 确定返回值和参数public void Traversal(TreeNode node,int depth){//2. 确定终止条件if(node.leftnullnode.right null){//叶子节点if(depthmaxDepth){//当前深度大于最大深度maxDepth depth;//记录当前深度为最大深度result node.val;}}//找左下角的值所以优先遍历左左子树if(node.left!null){depth;Traversal(node.left,depth);//回溯深度的值depth--;//精简代码 traversal(root-left, depth 1); 隐藏着回溯}//遍历右子树if(node.right!null){depth;Traversal(node.right,depth);depth--;}}
}112. 路径总和
题目给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。 示例一 输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22 输出true 解释等于目标和的根节点到叶节点路径如上图所示。 思路可以使用深度优先遍历的方式本题前中后序都可以无所谓因为中节点也没有处理逻辑来遍历二叉树
C#代码
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) {* this.val val;* this.left left;* this.right right;* }* }*/
public class Solution {public bool HasPathSum(TreeNode root, int targetSum) {if(root null) return false;targetSum - root.val;//确定终止条件if(root.left null root.right null){return targetSum 0;}if(root.left!null){if(HasPathSum(root.left,targetSum)) return true;}if(root.right!null){if(HasPathSum(root.right,targetSum)) return true;}return false;}
}113. 路径总和 II
题目给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。 示例一 输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 输出[[5,4,11,2],[5,8,4,5]] C#代码
public class Solution {ListIListint result new ListIListint();public IListIListint PathSum(TreeNode root, int targetSum) {var list new Listint();Traversal(root,targetSum,list);return result;}public void Traversal(TreeNode root, int targetSum,Listint list){if(root null) return;list.Add(root.val);targetSum - root.val;//到达叶子节点并且路径正确if(root.leftnullroot.rightnulltargetSum0){result.Add(new Listint(list.ToArray()));return;}if(root.left!null){Traversal(root.left,targetSum,list);//回溯list.RemoveAt(list.Count - 1);}if(root.right!null){Traversal(root.right,targetSum,list);//回溯list.RemoveAt(list.Count - 1);}}
}106. 从中序与后序遍历序列构造二叉树
题目给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例一 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出[3,9,20,null,null,15,7] 思路
通过后序序列可以知道最后一个元素为根结点。知道根结点后通过中序序列可以判断出根结点的左右子树。
解题过程
第一步如果数组大小为零的话说明是空节点了。第二步如果不为空那么取后序数组最后一个元素作为节点元素。第三步找到后序数组最后一个元素在中序数组的位置作为切割点第四步切割中序数组切成中序左数组和中序右数组 顺序别搞反了一定是先切中序数组第五步切割后序数组切成后序左数组和后序右数组第六步递归处理左区间和右区间
C#代码递归
public class Solution {public TreeNode BuildTree(int[] inorder, int[] postorder) {// 1. 如果后序数组元素为0则为空树if(postorder.Length0) return null;// 2. 取后序序列的最后一个元素得到根结点int rootVale postorder[postorder.Length - 1];TreeNode node new TreeNode(rootVale);if(postorder.Length 1) return node;// 3. 通过根结点找到中序序列的分割点下标int index;for(index 0; indexinorder.Length; index){if(inorder[index] rootVale){break;}}// 4. 分割左子树//左子树的中序序列int[] leftInorder new int[index];//遍历拷贝// for(int i 0;ileftInorder.Length;i){// leftInorder[i] inorder[i];// }//使用Array.Copy方法Array.Copy(inorder,0,leftInorder,0,leftInorder.Length);int[] leftPostorder new int[leftInorder.Length];// for(int i 0; ileftPostorder.Length;i){// leftPostorder[i] postorder[i];// }Array.Copy(postorder,0,leftPostorder,0,leftPostorder.Length);// 5. 分割右子树//右子树的中序序列int[] rightInorder new int[inorder.Length -(index1)];// for(int i 0;irightInorder.Length;i){// rightInorder[i] inorder[iindex1];// }Array.Copy(inorder,index1,rightInorder,0,rightInorder.Length);int[] rightPostorder new int[rightInorder.Length];// for(int i 0;irightPostorder.Length;i){// rightPostorder[i] postorder[ileftPostorder.Length];// }Array.Copy(postorder,leftPostorder.Length,rightPostorder,0,rightPostorder.Length);// 6. 递归左区间和右区间node.left BuildTree(leftInorder,leftPostorder);node.right BuildTree(rightInorder,rightPostorder);return node;}
}105. 从前序与中序遍历序列构造二叉树
题目给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例一 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 思路和后序遍历一样通过前序遍历的第一个元素可知根结点通过根结点和中序序列分割出左右子树通过递归即可构建出二叉树。
C#代码
public class Solution {public TreeNode BuildTree(int[] preorder, int[] inorder) {//1. 判断前序遍历长度if(preorder.Length 0) return null;//2. 获取根结点int rootVale preorder[0];TreeNode root new TreeNode(rootVale);if(preorder.Length 1) return root;//3. 获取根结点在中序序列中的下标int index;for(index 0;indexinorder.Length;index){if(inorder[index] rootVale){break;}}//4. 分割左子树int[] leftInorder new int[index];Array.Copy(inorder,0,leftInorder,0,index);int[] leftPreorder new int[leftInorder.Length];Array.Copy(preorder,1,leftPreorder,0,leftPreorder.Length);//5. 分割右子树int[] rightInorder new int[inorder.Length -(index1)];Array.Copy(inorder,index1,rightInorder,0,rightInorder.Length);int[] rigthPreorder new int[rightInorder.Length];Array.Copy(preorder,1leftPreorder.Length,rigthPreorder,0,rigthPreorder.Length);//6. 递归左区间和右区间root.left BuildTree(leftPreorder,leftInorder);root.right BuildTree(rigthPreorder,rightInorder);return root;}
}
