算法笔记|Day14二叉树IV

• ☆☆☆☆☆leetcode 513.找树左下角的值
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 112. 路径总和
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 113.路径总和II
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 106.从中序与后序遍历序列构造二叉树
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 105.从前序与中序遍历序列构造二叉树
• • 题目分析
  • 代码

☆☆☆☆☆leetcode 513.找树左下角的值

题目链接：leetcode 513.找树左下角的值

题目分析

本题递归+回溯，采用前序、中序、后序遍历均可，只需先处理左节点再处理右节点均可，不涉及中节点的处理逻辑；另外可以采用迭代层序遍历更简单。

代码

1.1递归 class Solution {     int maxDepth=Integer.MIN_VALUE;     int result;      public int findBottomLeftValue(TreeNode root) {         result=root.val;         traversal(root,0);         return result;     }      public void traversal(TreeNode root,int depth){         if(root==null)             return;         if(root.left==null&&root.right==null){             if(depth>maxDepth){                 maxDepth=depth;                 result=root.val;             }         }         if(root.left!=null){             depth++;             traversal(root.left,depth);             depth--;         }         if(root.right!=null){             depth++;             traversal(root.right,depth);             depth--;         }     } } 

1.2递归（精简版本） class Solution {     int maxDepth=Integer.MIN_VALUE;     int result;      public int findBottomLeftValue(TreeNode root) {         result=root.val;         traversal(root,0);         return result;     }      public void traversal(TreeNode root,int depth){         if(root==null)             return;         if(root.left==null&&root.right==null){             if(depth>maxDepth){                 maxDepth=depth;                 result=root.val;             }         }         if(root.left!=null)             traversal(root.left,depth+1);         if(root.right!=null)             traversal(root.right,depth+1);     } } 

2.迭代，层序遍历 class Solution {     public int findBottomLeftValue(TreeNode root) {         Deque deque=new LinkedList<>();         deque.add(root);         int res=0;         while(!deque.isEmpty()){             int size=deque.size();             for(int i=0;i                 TreeNode temp=deque.poll();                 if(i==0)                     res=temp.val;                 if(temp.left!=null)                     deque.add(temp.left);                 if(temp.right!=null)                     deque.add(temp.right);             }         }         return res;     } } 

☆☆☆☆☆leetcode 112. 路径总和

题目链接：leetcode 112. 路径总和

题目分析

本题递归+回溯，采用前序、中序、后序遍历均可，不涉及中节点的处理逻辑。

代码

1.1递归+回溯 class Solution {     public boolean hasPathSum(TreeNode root, int targetSum) {         if(root==null)             return false;         return traversal(root,targetSum-root.val);     }      public boolean traversal(TreeNode node,int count){         if(node==null)             return false;         if(node.left==null&&node.right==null&&count==0)             return true;         if(node.left==null&&node.right==null&&count!=0)             return false;         if(node.left!=null){             count-=node.left.val;             if(traversal(node.left,count))return true;             count+=node.left.val;         }         if(node.right!=null){             count-=node.right.val;             if(traversal(node.right,count))return true;             count+=node.right.val;         }         return false;     } } 

1.2递归+回溯（精简版本） class Solution {     public boolean 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;     } } 

1.3递归+回溯（更精简版本） 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);     } } 

☆☆☆☆☆leetcode 113.路径总和II

题目链接：leetcode 113.路径总和II

题目分析

递归+回溯，采用前序、中序、后序遍历均可，不涉及中节点的处理逻辑，要遍历所有路径所以递归函数不需要返回值。

代码

class Solution {     List> result;     List path;      public List> pathSum(TreeNode root, int targetSum) {         result=new LinkedList<>();         path=new LinkedList<>();         traversal (root,targetSum);         return result;     }      public void traversal(TreeNode root,int count){         if(root==null)             return;         path.add(root.val);         if(root.left==null&&root.right==null&&count==root.val)             result.add(new LinkedList<>(path));         traversal(root.left,count-root.val);         traversal(root.right,count-root.val);         path.removeLast();     } } 

☆☆☆☆☆leetcode 106.从中序与后序遍历序列构造二叉树

题目链接：leetcode 106.从中序与后序遍历序列构造二叉树

题目分析

递归采用前序遍历，重点在切割两个遍历序列，切割点在后序数组（左右中）的最后一个元素，就是用这个元素来切割中序数组（左中右），所以必要先切割中序数组，区分开左后序、右后序、左中序、右中序四个数组，此题采用左闭右开区间，决定了每个数组的收尾索引值。

代码

class Solution {     Map map;          public TreeNode buildTree(int[] inorder, int[] postorder) {         map=new HashMap<>();         for(int i=0;i         if(inBegin>=inEnd||postBegin>=postEnd)             return null;         int rootIndex=map.get(postorder[postEnd-1]);         TreeNode root=new TreeNode(inorder[rootIndex]);         root.left=findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+(rootIndex-inBegin));         root.right=findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+(rootIndex-inBegin),postEnd-1);         return root;     } } 

提示：inBegin >= inEnd || postBegin >= postEnd不满足左闭右开，说明没有元素，返回空树

☆☆☆☆☆leetcode 105.从前序与中序遍历序列构造二叉树

题目链接：leetcode 105.从前序与中序遍历序列构造二叉树

题目分析

递归采用前序遍历，重点在切割两个遍历序列，切割点在前序数组（中左右）的第一个元素，就是用这个元素来切割中序数组（左中右），所以必要先切割中序数组，区分开左前序、右前序、左中序、右中序四个数组，此题采用左闭右开区间，决定了每个数组的收尾索引值。

代码

class Solution {     Map map;      public TreeNode buildTree(int[] preorder, int[] inorder) {         map=new HashMap<>();         for(int i=0;i         if(preBegin>=preEnd||inBegin>=inEnd)             return null;         int rootIndex=map.get(preorder[preBegin]);         TreeNode root=new TreeNode(inorder[rootIndex]);         root.left=findNode(preorder,preBegin+1,preBegin+(rootIndex-inBegin)+1,inorder,inBegin,rootIndex);         root.right=findNode(preorder,preBegin+(rootIndex-inBegin)+1,preEnd,inorder,rootIndex+1,inEnd);         return root;     } } 

提示：preBegin>=preEnd||inBegin>=inEnd不满足左闭右开，说明没有元素，返回空树