算法——树（二）

标签：right return 算法 ans null root left

1、路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

 1 class Solution {
 2     boolean haspath=false;
 3     public boolean hasPathSum(TreeNode root, int targetSum) {
 4         if(root==null)return false;
 5         else{
 6             if(root.left==null&&root.right==null){
 7                 return root.val==targetSum;
 8             }
 9             return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
10         }
11     }
12 
13 }

View Code

2、翻转二叉树

 1 class Solution {
 2     public TreeNode invertTree(TreeNode root) {
 3         if(root==null)return root;
 4         TreeNode tmp=root.left;
 5         root.left=root.right;
 6         root.right=tmp;
 7         root.left=invertTree(root.left);
 8         root.right=invertTree(root.right);
 9         return root;
10 
11     }
12 }

View Code

3、二叉树的所有路径

bfs

 1 //bfs
 2 class Solution {
 3     public List<String> binaryTreePaths(TreeNode root) {
 4         
 5         List<String> ans=new ArrayList<>();
 6         if(root==null)return ans;
 7         Queue<TreeNode> queue=new ArrayDeque<>();
 8         Queue<String> paths=new ArrayDeque<>();
 9         queue.add(root);
10         paths.add(Integer.toString(root.val));
11         while(!queue.isEmpty()){
12             TreeNode tmp=queue.poll();
13             String path=paths.poll();
14             if(tmp.left==null&&tmp.right==null){
15                 ans.add(path);
16             }else{
17                 if(tmp.left!=null){
18                     paths.offer(new StringBuffer(path).append("->").append(tmp.left.val).toString());
19                     queue.offer(tmp.left);
20                 }
21                 if(tmp.right!=null){
22                     paths.offer(new StringBuilder(path).append("->").append(tmp.right.val).toString());
23                     queue.offer(tmp.right);
24                 }
25             }
26         }
27         return ans;
28 
29     }
30 }

View Code

dfs递归：

 1 //dfs
 2 class Solution {
 3     public List<String> binaryTreePaths(TreeNode root) {
 4         
 5         List<String> ans=new ArrayList<>();
 6         if(root==null)return ans;
 7         dfs(root,ans,"");
 8         return ans;
 9     }
10     public void dfs(TreeNode root,List<String> ans,String path){
11         if(root!=null){
12             StringBuilder sb=new StringBuilder(path);
13             sb.append(root.val);
14             if(root.left==null&& root.right==null){
15                 ans.add(sb.toString());
16             }            
17             sb.append("->");
18             dfs(root.left,ans,sb.toString());
19             dfs(root.right,ans,sb.toString());
20 
21         }
22     } 
23 }

View Code

dfs 栈：

 1 class Solution {
 2     public List<String> binaryTreePaths(TreeNode root) {
 3         
 4         List<String> ans=new ArrayList<>();
 5         if(root==null)return ans;
 6         Deque<TreeNode> stack=new LinkedList<>();
 7         Deque<String> paths=new LinkedList<>();
 8         stack.push(root);
 9         paths.push(Integer.toString(root.val));
10         while(!stack.isEmpty()){
11             TreeNode node=stack.pop();
12             String path=paths.pop();
13             if(node.left==null&&node.right==null){
14                 ans.add(path);
15             }
16             if(node.left!=null){
17                 stack.push(node.left);
18                 paths.push(new StringBuilder(path).append("->").append(node.left.val).toString());
19             }
20             if(node.right!=null){
21                 stack.push(node.right);
22                 paths.push(new StringBuilder(path).append("->").append(node.right.val).toString());
23             }
24         }
25         return ans;
26     }
27 
28 }

View Code

4、左叶子之和

 1 class Solution {
 2     int result = 0;
 3     public int sumOfLeftLeaves(TreeNode root) {
 4         if (root == null) {
 5             return 0;
 6         }
 7         dfs(root, 0);
 8         return result;
 9     }
10 
11     void dfs(TreeNode root, int direction) {
12         if (root == null) {
13             return;
14         }
15         if (direction == 1 && root.left == null && root.right == null) {
16             result += root.val;
17         }
18         // 1：向左， 2：向右
19         dfs(root.left,  1);
20         dfs(root.right, 2);
21     }
22 }

View Code

5、合并二叉树

 1 class Solution {
 2     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
 3         if(root1==null&&root2==null){
 4             return null;
 5         }else{
 6             if(root1==null)return root2;
 7             if(root2==null)return root1;
 8             else{
 9                 root1.val=root1.val+root2.val;
10                 root1.left=mergeTrees(root1.left,root2.left);
11                 root1.right=mergeTrees(root1.right,root2.right);
12                 return root1;
13             }
14         }
15 
16     }
17 }

View Code

6、N叉树的最大高度

 1 class Solution {
 2     public int maxDepth(Node root) {
 3         if(root==null)return 0;
 4         int max=0;
 5         for(Node child:root.children){
 6             max=Math.max(maxDepth(child),max);
 7         }
 8         return max+1;
 9         
10     }
11 }

View Code

 

标签：right,return,算法,ans,null,root,left
From： https://www.cnblogs.com/coooookie/p/17483974.html