乐趣区

关于二叉树:leetcode-二叉树

jiezi

144. 二叉树的前序遍历

  1. 递归

JAVA 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();
        return help(root, res);
    }
    public List<Integer> help (TreeNode root, List<Integer> list){if (root != null) {list.add(root.val);
            help(root.left, list);
            help(root.right, list);
        }
        return list;
        
    }    
}
  1. 迭代

借用栈

因为二叉树的前序遍历有往回走的过程，因而思考用栈构造。
同时先拜访左孩子后拜访右孩子，因而入栈程序为先右孩子入栈后左孩子入栈。
JAVA 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */
class Solution {public List<Integer> preorderTraversal(TreeNode root) {if (root==null) return new ArrayList<Integer>();
        
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        
        // 拜访栈节点并弹出，先右孩子入栈，后左孩子入栈
        while(!stack.isEmpty()){TreeNode top = stack.pop();
            res.add(top.val);
            
            if (top.right!=null){stack.push(top.right);
            }
            if (top.left!=null){stack.push(top.left);
            }
        }
        return res;

    }
}

94. 二叉树的中序遍历

  1. 递归

JAVA 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();
        res = help(root, res);
        return res;

    }
    
    public List<Integer> help(TreeNode root, List<Integer> list){if (root!=null){help(root.left, list);
            list.add(root.val);
            help(root.right, list);
            return list;
        }
        return list;
    }
}
  1. 迭代

还是用栈

  • 拜访左侧链的最初一个节点 (左侧链节点入栈)
  • 转向该节点的右子树
  • 拜访该子树上左侧链的最初一个节点 (右子树左侧链节点入栈)

JAVA 代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
       
        while(!stack.isEmpty()){
            // 左侧链入栈：左孩子不为空则入栈
            if (root.left != null){
                root = root.left;
                stack.push(root);
            }
            else{ // 否则拜访左侧链最初一个节点，即栈顶元素
                TreeNode top = stack.pop();
                res.add(top.val);
                if (top.right!=null){
                    root = top.right;
                    stack.push(root);
                }
            }
        }
        return res;
    }
}

145. 二叉树的后序遍历

  1. 递归

JAVA 代码

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();
        res = help(root, res);
        return res;
    }
    
    public List<Integer> help(TreeNode root, List<Integer> list){if (root!=null){help(root.left,list);
            help(root.right, list);
            list.add(root.val);
        }
        return list;
    }
}
  1. 迭代


因为前序 (中左右) 和中序 (左中右) 遍历要求每个节点要拜访两遍，因而能够用栈实现。
后序遍历要求每个节点拜访三次，因而须要借用两个栈。
根右左 的逆序是 左右根 ，即为后序遍历。
而前序遍历为 根左右 ，只有前序遍历的过程改为先拜访右孩子再拜访左孩子，即为根右左.
因而能够思考依照 根右左 的程序拜访节点，将拜访的节点装入另一个栈中再弹出，程序即为左右根.
留神的中央：因为须要失去 根右左 的程序，因而入栈程序为先入左孩子后入右孩子。

JAVA 代码

// 迭代
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();
        if (root==null) return res;
        
        Stack<TreeNode> stack1 = new Stack<>();  // 根右左: 因而入栈程序为先左孩子入栈，后右孩子入栈
        Stack<TreeNode> stack2 = new Stack<>();
        
        stack1.add(root);
        while(!stack1.isEmpty()){root = stack1.pop();
            stack2.add(root);
            if(root.left!=null){   // 左孩子入栈
                stack1.add(root.left);
            }
            if(root.right!=null){  // 右孩子入栈
                stack1.add(root.right);
            }
        }
        while(!stack2.isEmpty()){res.add(stack2.pop().val);
        }
        return res;
    }
}

档次遍历

利用队列：先进先出
若拜访以后节点，若左孩子存在，左孩子入栈；若右孩子存在，右孩子入栈.

JAVA 代码

public class BTree_LevelOrder {public List<Integer> levelOrder(TreeNode root){List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){root = queue.poll();
            res.add(root.val);
            if (root.left!=null) queue.offer(root.left);   // 若左孩子不为空，左孩子入队
            if (root.right!=null) queue.offer(root.right); // 若右孩子不为空，右孩子入队
        }
        return res;
    }
  }

工夫复杂度：O(n)
空间复杂度：O(n)

102. 二叉树的档次遍历

给定一个二叉树，返回其按档次遍历的节点值。（即逐层地，从左到右拜访所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其档次遍历后果：

[[3],
  [9,20],
  [15,7]
]

题解：

  1. 思路一

递归：先序遍历
借用一个 help 递归函数，传的值为：以后节点，以后节点的层数

  • 根节点为空，返回空的 List
  • 第 0 层只蕴含一个根节点 root.
  • 若以后节点的层数大于 list 的个数，则减少一个空的 list
  • 以后节点位于第几层就将该节点放进第几个 list 中.
  • 递归以后节点的左孩子和右孩子，此时层数增 1

JAVA 代码

class Solution {List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {if (root==null) return res;
            help(root, 0);
            return res;
    }
    
    public void help(TreeNode root, int level){if (res.size()-1<level){         // 若最高层数小于以后层数，则 res 中再减少一个列表来装这一层的节点值
            res.add(new ArrayList<Integer>());  
        }
        res.get(level).add(root.val);  // 对应的 list 装对应层的节点值
        
        if (root.left!=null){help(root.left, level+1);
        }
        if (root.right!=null){help(root.right, level+1);
        }
    }
}

工夫复杂度：O(n)
空间复杂度: O(n) 输入的数组蕴含 n 个值

  1. 思路二

BFS 迭代，借用队列

  • 根节点为空时，返回空数组

  • 根节点不空时，初始节点为 root，入队，层数为 0

    • 每到新的一层减少一个新的空数组
    • 以后层的节点即为以后队列中的所有节点，将队列中的节点逐个弹出并放入数组中，并将以后节点的左孩子右孩子放入队列中，level+1
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();
            if (root==null) return res;
            
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int level = 0;  // 初始时 root 为第 0 层
            while(!queue.isEmpty()){res.add(new ArrayList<Integer>());
                
                // 以后层节点即为队列中的节点
                int len = queue.size();
                // 以后层节点退出数组
                for (int i=0; i<len; i++){root = queue.poll();
                    res.get(level).add(root.val);
                    if (root.left!=null) queue.offer(root.left);
                    if (root.right!=null) queue.offer(root.right);
                }
                level++;
            }
            return res;
    }
}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长门路上的节点数。

阐明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3。
题解：

  1. 思路一

递归
根节点的深度等于左右子树中最深子树的高度 +1
JAVA 代码

class Solution {public int maxDepth(TreeNode root) {if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
}

工夫复杂度：O(n)
空间复杂度：O(n)

  1. 思路二

BFS 迭代：档次遍历，借用队列
队列的每个元素记录了：key: 以后节点，value: 以后节点间隔根节点的间隔

  • 根节点为空时，高度为 1
  • 根不为空时，根节点的 value 为 1

每次，以后节点的左右孩子入队时，间隔增 1

JAVA 代码

class Solution {public int maxDepth(TreeNode root) {Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>(); // 队列模式{"节点"，"间隔根节点的间隔"}
        if (root==null) return 0;
        queue.offer(new Pair(root,1));
        int max = 1;
        while(!queue.isEmpty()){Pair<TreeNode,Integer> current = queue.poll();// 以后节点
            root = current.getKey();
            int depth = current.getValue(); // 以后节点间隔根节点的间隔
            max = Math.max(max, depth);

            if (root.left!=null)
                queue.offer(new Pair(root.left,depth+1));
            if (root.right!=null)
                queue.offer(new Pair(root.right, depth+1));
        }
        return max;
    }
}

工夫复杂度：O(n)
空间复杂度：O(n)

  1. 思路三

DFS 迭代：先序遍历，利用栈
栈的每个元素记录了：key: 以后节点，value: 以后节点间隔根节点的间隔

  • 根节点为空时，高度为 1
  • 根不为空时，根节点的 value 为 1

每次，以后节点的右和左孩子入栈时，间隔增 1

JAVA 代码

//DFS: 先序遍历
class Solution {public int maxDepth(TreeNode root) {Stack<Pair<TreeNode, Integer>> stack = new Stack<>(); // 队列模式{"节点"，"间隔根节点的间隔"}
        if (root==null) return 0;
        stack.push(new Pair(root,1));
        int max = 1;
        while(!stack.isEmpty()){Pair<TreeNode,Integer> current = stack.pop();// 以后节点
            root = current.getKey();
            int depth = current.getValue(); // 以后节点间隔根节点的间隔
            max = Math.max(max, depth);

            if (root.right!=null)
                stack.push(new Pair(root.right,depth+1));
            if (root.left!=null)
                stack.push(new Pair(root.left, depth+1));
        }
        return max;
    }
}

工夫复杂度：O(n)
空间复杂度：齐全不均衡时最坏 O(n)，齐全均衡时最好 O(logn)

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短门路上的节点数量。

阐明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度 2.
题解：

  1. 递归

分三种状况：

  • 以后节点只有左子树，返回左子树的高度 +1
  • 以后节点只有右子树，返回右子树的高度 +1
  • 以后节点又有左子树又有右子树，返回矮的那棵树的高度 +1
class Solution {public int minDepth(TreeNode root) {if (root == null) return 0;
        // 如果只有右子树，返回右子树的高度 +1
        if (root.left==null && root.right!=null) return minDepth(root.right)+1;
        // 如果只有左子树，返回左子树的高度 +1
        if (root.right==null && root.left!=null) return minDepth(root.left)+1;
        // 既有左子树又有右子树，返回左子树和右子树中较矮的高度 +1
        return Math.min(minDepth(root.left),minDepth(root.right))+1;
    }
}

工夫复杂度：O(n)
空间复杂度：最好 O(logn)，最坏 O(logn)

  1. DFS 先序迭代，相似 104
  2. BFS 队列，相似 104

285 二叉搜寻树中的中序后继

【题目】当初有一种新的二叉树节点类型如下：

public class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {this.value = data;}
}

    该构造比一般二叉树节点构造多了一个指向父节点的 parent 指针。

假如有一 棵 Node 类型的节点组成的二叉树，
树中每个节点的 parent 指针都正确地指向本人的父节点，
头节点的 parent 指向 null。只给一个在二叉树中的某个节点 node，
请实现返回 node 的后继节点的函数。在二叉树的中序遍历的序列中，node 的下一个节点叫作 node 的后继节。

解答：

  1. 后继节点：依照中序遍历的程序 左根右
  2. 若以后节点有右孩子，那么它的后继节点为右子树左侧链的最初一个节点
  3. 若以后节点没有右孩子，那么始终找父节点，节点在父节点的左子树中，则该父节点为其后继节点。

留神的中央：查看某一结点是否是某父节点左子树的中的节点，只需设一个长期指针 p，初始时 p 为以后节点，而后查看 p 的父节点的左孩子是否为 p, 若是，则该父节点为后继，否则 p 指向该父节点，持续找下一个父节点，晓得找到根节点。

前驱节点

  1. 若该节点有左孩子，则前驱为左子树最右的节点
  2. 若该节点没有左孩子，那么始终往上找一个父节点，节点在父节点的右子树中，该父节点为其前驱节点。

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为间断的比特位的操作，进而能够将转换后的数据存储在一个文件或者内存中，同时也能够通过网络传输到另一个计算机环境，采取相同形式重构失去原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只须要保障一个二叉树能够被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你能够将以下二叉树：1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提醒: 这与 LeetCode 目前应用的形式统一，详情请参阅 LeetCode 序列化二叉树的格局。你并非必须采取这种形式，你也能够采纳其余的办法解决这个问题。

阐明: 不要应用类的成员 / 全局 / 动态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

解答：

  1. 思路一：

先序遍历形式，遇到空时，将空字符也退出序列。

public class BinaryTree_Serialize_Deserialize {
        /****************** 二叉树 => 字符串 *********************/
        public static String serialize(TreeNode root){if (root==null) return "null,";
            String str = Integer.toString(root.val)+",";
            str += serialize(root.left);
            str += serialize(root.right);
            return str;

        }
        /******************* 字符串 => 二叉树 *******************/
        public TreeNode deserialize(String data){String[] data_array = data.split(",");  // 依照 "," 切分
            Queue<String> queue = new LinkedList<>();
            // 将元素装入队列
            for (int i=0; i<data_array.length; i++){queue.offer(data_array[i]);
            }
            return deserialize_preOrder(queue);
        }

        // 中序形式将字符串转化为二叉树
        public TreeNode deserialize_preOrder(Queue<String> queue){String val = queue.poll();
            if (val.equals("null")) return null;
            TreeNode root = new TreeNode(Integer.valueOf(val));
            root.left = deserialize_preOrder(queue);
            root.right = deserialize_preOrder(queue);
            return root;
        }
      }
  1. 思路二：

中序遍历形式、后序遍历

3. 思路三：
层序遍历

110. 均衡二叉树

树形动静布局
给定一个二叉树，判断它是否是高度均衡的二叉树。
本题中，一棵高度均衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true。

解答：

  1. 思路一

自底向下
（1) 判断左子数是否均衡，若不是间接返回 false
（2）判断右子树是否均衡，若不是间接返回 false
（3）左子树的高度
（4）右子树的高度
若左均衡，右均衡, 且左子树的高度与右子树的高度差 1，则该子树均衡.

class Solution {public boolean isBalanced(TreeNode root) {return recur(root) != -1;
    }
    
    public int recur(TreeNode root){if (root == null) return 0;  // 根节点若为空，则返回高度为 0
        int left = recur(root.left);
        if (left == -1) return -1; // 若左子树不均衡，返回 -1
        int right = recur(root.right);
        if (right == -1) return -1; // 若右子树不均衡，返回 -1
        
        // 若左右均衡且高度相差小于 2，则整颗树均衡，高度为较高子树高度 +1，// 若左右均衡且高度相差小于 2，则整棵树不均衡，返回 -1
        return Math.abs(left-right)<2? Math.max(left, right)+1: -1;
    }
}

工夫复杂度 O(n)
空间复杂度 O(n)

  1. 思路二

自顶向下
每一个节点左子树高度与右子树高度差都小于 2，则整棵树为均衡树。
需要求每个节点的高度，造成冗余。

class Solution {public boolean isBalanced(TreeNode root) {if (root==null) return true;
        return Math.abs(depth(root.left)-depth(root.right))<2 && isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int depth(TreeNode root){if (root == null) return 0;
        return Math.max(depth(root.left),depth(root.right)) + 1;
    }
}

工夫复杂度：O(nlogn)
空间复杂度：O(n)

958. 二叉树的完全性测验

给定一个二叉树，确定它是否是一个齐全二叉树。

百度百科中对齐全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都间断集中在最右边，这就是齐全二叉树。（注：第 h 层可能蕴含 1~ 2h 个节点。）
示例 1：

输出：[1,2,3,4,5,6]
输入：true
解释：最初一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最初一层中的所有结点（{4,5,6}）都尽可能地向左。

题解：
按层遍历

    1. 一个节点没有左孩子，有右孩子，肯定不是齐全二叉树，间接返回false
    1. 不满足 1. 的条件下，一个节点不是左右孩子双全时（有左没右，或没左没右），且前面遇到的都是叶子，则是齐全二叉树，返回true. 若前面不都是叶子，返回false


JAVA 代码

class Solution {public boolean isCompleteTree(TreeNode root) {if (root == null) return true;
        boolean leaf = false;
        
        // 层遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){root = queue.poll();
            //3. 后面呈现左右孩子双全的节点，若以后节点不是叶子，返回 false
            //2. 或者以后节点没有左孩子，但有右孩子，返回 false
            if ((leaf && (root.left!=null || root.right!=null))  //
                ||(root.left==null && root.right!=null)){return false;}
            
            if (root.left!=null) queue.offer(root.left);
            if (root.right != null) queue.offer(root.right);  
            else leaf = true;   //1. 当不是左右孩子双全时，前面遍历的节点必须是叶子的状况开启
        }
        return true;
    }
}

工夫复杂度：每个节点拜访一下 O(n)
空间复杂度：树的最大宽度 O(w)

222. 齐全二叉树的节点个数

给出一个齐全二叉树，求出该树的节点个数。
阐明：
齐全二叉树的定义如下：在齐全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最上面一层的节点都集中在该层最右边的若干地位。若最底层为第 h 层，则该层蕴含 1~ 2h 个节点。
示例:

输出: 
    1
   / \
  2   3
 / \  /
4  5 6
输入: 6

题解：
来自左 chengyun 的思路

  1. 求出树高h：只需遍历左侧链
  2. 求出右子树的高度：

  • 等于h-1:

    • 左子树是齐全二叉树，左子树 + 根节点个数：2^(h-1) -1+1
    • 右子树递归计算节点个数

  • 等于h-2:

    • 右子树是齐全二叉树，右子树 + 根节点个数：2^(h-2) -1+1
    • 左子树递归计算节点个数

递归函数 bfs: root- 以后子树根节点，level– 以后子树根节点层数，h- 树总高，返回以后子树总节点数。
计算子树高度函数leLftLevel

JAVA 代码

class Solution {public int countNodes(TreeNode root) {if (root == null) return 0;
        int h = leftLevel(root, 1);
        return bfs(root, 1, h);
    }
    public int bfs(TreeNode root, int level, int h){if (level == h) return 1; // 留神的点
        // 左子树齐全二叉
        if (leftLevel(root.right, level+1) == h){return  (1<<(h-level)) + bfs(root.right, level+1, h);
        }
        else { // 右子树齐全二叉
            return (1<<(h-level-1))+bfs(root.left, level+1, h);
        }
    }
    
    // 遍历左侧链，失去子树高度
    public static int leftLevel(TreeNode root, int level){while (root!=null){
            level++;
            root = root.left;
        }
        return level-1;
    }
}

门路

112. 门路总和

给定一个二叉树和一个指标和，判断该树中是否存在根节点到叶子节点的门路，这条门路上所有节点值相加等于指标和。

阐明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及指标和 sum = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回 true, 因为存在指标和为 22 的根节点到叶子节点的门路 5->4->11->2。
解答：

  1. DFS 递归：先序
  • 当根节点为空时，返回 false

  • 当根节点为空时，

    • 以后节点不为叶子，对左、右孩子调用 hasPathSum 函数：通过递归 left || right，其中 sum 值减去以后节点的权值。
    • 以后节点为叶子，且 sum 值为 0 时，为无效门路。否则门路有效。
class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root==null) return false;
        sum -=root.val;
        if (root.left==null&& root.right==null && sum==0)
            return true;
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

工夫复杂度：O(n)
空间复杂度：最坏 O(n), 最好 O(logn)

  1. DFS 迭代

借用栈，栈元素: {root, sum-val}
栈中寄存节点及对应的 sum，以后节点为叶子且 sum 值为 0 时，为无效门路。

  • 根节点为空时，返回 false

  • 根节点不为空时，

    • 初始时，{root, sum-root.val} 入栈
    • 当栈不空时，先序遍历形式右孩子先进，左孩子后进
      同时以后节点为空，且 sum 值减到 0 时，为无效门路。

JAVA 代码

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) return false;
            
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        sum = sum - root.val;
        stack.push(new Pair(root,sum));

        while(!stack.isEmpty()){Pair<TreeNode, Integer> current = stack.pop();
            root = current.getKey();
            sum = current.getValue();
            
            if (root.left==null && root.right==null && sum==0){return true;}
            if (root.right!=null) stack.push(new Pair(root.right, sum-root.right.val));
            if (root.left!=null) stack.push(new Pair(root.left, sum-root.left.val));

        }
        return false;
    }
}

工夫复杂度：O(n)
空间复杂度：最坏 O(n), 最好 O(logn)

437. 门路总和 III

给定一个二叉树，它的每个结点都寄存着一个整数值。

找出门路和等于给定数值的门路总数。

门路不须要从根节点开始，也不须要在叶子节点完结，然而门路方向必须是向下的（只能从父节点到子节点）。

二叉树不超过 1000 个节点，且节点数值范畴是 [-1000000,1000000] 的整数。

示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的门路有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

题解：
递归办法：
因为门路不肯定从根节点开始，任何一个节点都可能开始，也不须要在叶子节点完结。
状况分为包含以后根节点的门路和不包含根节点的门路。

class Solution {public int pathSum(TreeNode root, int sum) {
        int num = 0;
        if (root == null) return num;
        if (root.val == sum) num +=1;
        
        // 与 root 无关的门路
        num += pathSum(root.left, sum);
        num += pathSum(root.right, sum);
        
        // 与 root 无关的门路，不能间接递归 pathSum, 会呈现断路的状况
        num += pathSum_root(root.left, sum-root.val);
        num += pathSum_root(root.right, sum-root.val);
        return num;
    }
    public int pathSum_root(TreeNode root, int sum) {if (root == null) return 0;
        int num = 0;
        if (root.val == sum) num += 1;
        
        // 与 root 无关的门路
        num += pathSum_root(root.left, sum-root.val);
        num += pathSum_root(root.right, sum-root.val);
        return num;
    }
}

【自我总结（不肯定正确）】
工夫复杂度：每个节点都要作为终点计算一次门路 O(n), 每个节点计算门路工夫复杂度 O(logn)

                  所以工夫复杂度为 O(nlogn)
                  空间复杂度: O(n)

“须要进一步看题解，当初看不懂，前面再看”

687. 最长同值门路

给定一个二叉树，找到最长的门路，这个门路中的每个节点具备雷同值。这条门路能够通过也能够不通过根节点。
留神：两个节点之间的门路长度由它们之间的边数示意。

示例 1:

输出:

              5
             / \
            4   5
           / \   \
          1   1   5
输入:

2

示例 2:

输出:

              1
             / \
            4   5
           / \   \
          4   4   5
输入:

2

还有其余门路题，别忘了。

543. 二叉树的直径

给定一棵二叉树，你须要计算它的直径长度。一棵二叉树的直径长度是任意两个结点门路长度中的最大值。这条门路可能穿过也可能不穿过根结点。
示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5

返回 3, 它的长度是门路 [4,2,1,3] 或者 [5,2,1,3]。
留神：两结点之间的门路长度是以它们之间边的数目示意。

// 一条门路的长度为该门路通过的节点数减一
// 最长门路：max{左子树最长门路，右子树最长门路，通过根节点的最长门路}
//=》最长门路：max{左子树最长门路，右子树最长门路，左子树深度 + 右子树深度}
class Solution {
    int diameter = 0;  // 应用全局变量保留拜访过的节点中的最长门路
    public int diameterOfBinaryTree(TreeNode root) {if (root==null) return 0;
        depth(root);
        return  diameter;
    }
    // 求以后子树高度
    public int  depth(TreeNode root){if (root==null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        diameter = Math.max(left+right, diameter);
        return 1+Math.max(left,right);
    }
}

226. 翻转二叉树

翻转一棵二叉树。

示例：

输出：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输入：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

617. 合并二叉树

给定两个二叉树，设想当你将它们中的一个笼罩到另一个上时，两个二叉树的一些节点便会重叠。
你须要将他们合并为一个新的二叉树。合并的规定是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将间接作为新二叉树的节点。

示例 1:

输出: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输入: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7

留神: 合并必须从两个树的根节点开始。

572. 另一个树的子树

给定两个非空二叉树 s 和 t，测验 s 中是否蕴含和 t 具备雷同构造和节点值的子树。s 的一个子树包含 s 的一个节点和这个节点的所有子孙。s 也能够看做它本身的一棵子树。

示例 1:

给定的树 s:

     3
    / \
   4   5
  / \
 1   2
给定的树 t：4 
  / \
 1   2
返回 true，因为 t 与 s 的一个子树领有雷同的构造和节点值。

示例 2:

给定的树 s：3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t：4
  / \
 1   2

101. 对称二叉树

给定一个二叉树，查看它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

然而上面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

阐明:

如果你能够使用递归和迭代两种办法解决这个问题，会很加分。

404. 左叶子之和

计算给定二叉树的所有左叶子之和。

示例：

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，别离是 9 和 15，所以返回 24

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈屋宇后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，咱们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪慧的小偷意识到“这个中央的所有屋宇的排列相似于一棵二叉树”。如果两个间接相连的房子在同一天早晨被打劫，屋宇将主动报警。
计算在不触动警报的状况下，小偷一晚可能盗取的最高金额。

示例 1:

输出: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输入: 7 
解释: 小偷一晚可能盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输出: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输入: 9
解释: 小偷一晚可能盗取的最高金额 = 4 + 5 = 9.

671. 二叉树中第二小的节点 (简略)

给定一个非空非凡的二叉树，每个节点都是负数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你须要输入所有节点中的第二小的值。如果第二小的值不存在的话，输入 -1。

示例 1:

输出: 
    2
   / \
  2   5
     / \
    5   7

输入: 5
阐明: 最小的值是 2，第二小的值是 5。

示例 2:

输出: 
    2
   / \
  2   2

输入: -1
阐明: 最小的值是 2, 然而不存在第二小的值。

637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

示例 1:

输出:
    3
   / \
  9  20
    /  \
   15   7
输入: [3, 14.5, 11]
解释:
第 0 层的平均值是 3,  第 1 层是 14.5, 第 2 层是 11. 因而返回 [3, 14.5, 11].

留神：节点值的范畴在 32 位有符号整数范畴内。
题解：
1. 思路一：DFS 递归
递归遍历二叉树，用两个数组别离记录每一层的总值和节点的总个数.
须要一个新的递归函数来实现：help()，参数有：
root: 以后节点值
sum: 每一层的总值，第 i 层的值累加到第 i 个元素中
count: 每一层节点总个数，第 i 层的个数累加到第 i 个元素中
i：以后节点所在层数，每次向下遍历层数增 1.

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();
        //List<Double> sum = new ArrayList<>();  // 节俭一个变量空间
        List<Integer> count = new ArrayList<>();
        help(root, 0, res, count);
        for (int i=0; i<res.size(); i++){res.set(i, res.get(i)/count.get(i));
        }
        return res;
    }
    
    public void help(TreeNode root, int i, List<Double> sum, List<Integer> count){if (root==null) return ;
        if (i < sum.size()){sum.set(i, sum.get(i) + root.val);
            count.set(i, count.get(i) + 1);
        }else{sum.add(1.0*root.val);
            count.add(1);
        }
        help(root.left, i+1, sum, count);  // 向下遍历，层数 +1
        help(root.right, i+1, sum, count);  // 向下遍历，层数 +1
    }
}

工夫复杂度：O(n)
空间复杂度：O(h)
2. BFS：借用队列
应用两个队列：一个队列寄存以后层节点，一个长期队列寄存下一层节点。
下一次层节点时，即拜访长期队列中寄存的节点。

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){  // 以后层节点不空
            int count = 0;
            long sum = 0;  // 留神：sum 为长整型
            Queue<TreeNode> temp = new LinkedList<>();  // 装下一层节点的队列
            while(!queue.isEmpty()){  // 以后层节点不空
                root = queue.poll();
                sum += root.val;
                count++;
                // 下一层节点入长期队列
                if (root.left!=null) temp.offer(root.left);
                if (root.right!=null) temp.offer(root.right);
            }
            // 以后层平均值
            res.add(1.0*sum/count);
            // 开始遍历下一层
            queue = temp;
        }
        return res;
    }
}

工夫复杂度：O(n)
空间复杂度：O(w)

513. 找树左下角的值 (中等)

给定一个二叉树，在树的最初一行找到最右边的值。

示例 1:

输出:

    2
   / \
  1   3

输入:
1

示例 2:

输出:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输入:
7

留神: 您能够假如树（即给定的根节点）不为 NULL。
题解：
1. 思路一：DFS 递归
借助一个二维数组，每一行元素保留对应层的所有结点，最初一行元素的第一个结点即为最初一层的最左结点。

class Solution {public int findBottomLeftValue(TreeNode root) {List<List<TreeNode>> array = new ArrayList<>(); 
        List<TreeNode> subArray = new ArrayList<>();
        help(root, 0, array, subArray);
        return array.get(array.size()-1).get(0).val;
    }
    public void help(TreeNode root, int i, List<List<TreeNode>> array, List<TreeNode> subArray){if (root==null) return;
        
        if (i<array.size()){subArray.add(root);
        }else{subArray = new ArrayList<>();
            subArray.add(root);
            array.add(subArray);
        }
        
        help(root.left, i+1, array, subArray);
        help(root.right, i+1, array, subArray);
        
    }
}

工夫复杂度 O（n）
空间复杂度 O（n）
2. 思路二：DFS
记录深度达到最大时的第一个结点：当达到的深度大于目前的最大深度时，为第一次达到该最大深度，最大深度更新。

class Solution {
    int maxLevel = -1;
    int leftVal = 0;
    public int findBottomLeftValue(TreeNode root) {help (root, 0);
      return leftVal;
    }
    public void help(TreeNode root, int i){if (root==null) return;
        
        if (i>maxLevel){
            maxLevel = i;
            leftVal = root.val;
        }
        help(root.left, i+1);
        help(root.right, i+1); 
    }
}

工夫复杂度 O(n)
空间复杂度 O(h)
3. 思路三：BFS
利用队列，每一层从右向左遍历，最初遍历到的最初一个结点即为最初一层最左的结点。

class Solution {public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){root = queue.poll();
            if (root.right!=null){queue.offer(root.right);
            }
            if (root.left!=null){queue.offer(root.left);
            }
        }
        return root.val;
    }
}

工夫复杂度 O(n)
工夫复杂度 O(w)

236. 二叉树的最近公共先人

1. 思路一：DFS 递归

  • 以后左子树有 p 和q，则在左子树找
  • 以后右子树有 p 和q，则在右子树找
  • 否则以后节点就是最近公共先人节点
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) return null;
        if (hasNode(root.left,p) && hasNode(root.left,q))  // 左子树有节点 p 和 q，则最近先人在左子树找
            return lowestCommonAncestor(root.left,p,q);
        else if (hasNode(root.right,p) && hasNode(root.right,q))  // 右子树有节点 p 和 q，则最近先人在右子树找
            return lowestCommonAncestor(root.right,p,q);
        return root;  // 否则以后节点为最近先人节点
        
    }
    // 子树中是否存在节点 t
    public boolean hasNode(TreeNode node, TreeNode t){if (node == null) return false;
        if (node.val == t.val) return true;
        return help(node.left,t) || help(node.right,t);
    }
}

工夫复杂度：O(n^2)
空间复杂度：O(h)

  1. 思路二：

这个函数的性能有三个：给定两个节点 p 和 q

如果 p 和 q都存在，则返回它们的公共先人；
如果只存在一个，则返回存在的一个；
如果 p和 q都不存在，则返回 NULL

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) return null;
        
        if (root == p || root == q) return root;
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left == null) return right;
        if (right == null) return left;
        if (left!=null && right!=null) return root;
        
        return null;
    }
}

工夫复杂度：O(n)
空间复复杂度：O(h)

617 合并二叉树

给定两个二叉树，设想当你将它们中的一个笼罩到另一个上时，两个二叉树的一些节点便会重叠。
你须要将他们合并为一个新的二叉树。合并的规定是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将间接作为新二叉树的节点。

示例 1:

输出: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输入: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7
留神: 合并必须从两个树的根节点开始。

递归

class Solution {public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {TreeNode root = new TreeNode();
        if (t1 == null && t2 == null){return null;}
        if (t1 !=null && t2 == null){return t1;}
        else if(t1==null && t2!=null){return t2;}
        else if(t1!=null && t2!=null){
            root.val = t1.val + t2.val;
            root.left = mergeTrees(t1.left, t2.left);
            root.right = mergeTrees(t1.right, t2.right);
            return root;
        }
        return root;
    }
}

档次遍历

class Solution {public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {TreeNode root = new TreeNode();
        if (t1 == null && t2 == null) return null;
        if (t1 != null && t2 == null) return t1;
        if (t1 == null && t2 != null) return t2;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(t1);
        queue.offer(t2);
        while(!queue.isEmpty()){TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            node1.val += node2.val;
            if (node1.left==null && node2.left!=null){node1.left = node2.left;}
            else if(node1.left!=null && node2.left!=null){queue.offer(node1.left);
                queue.offer(node2.left);
            }
            
            if (node1.right==null && node2.right!=null){node1.right = node2.right;}
            else if (node1.right!=null && node2.right!=null){queue.offer(node1.right);
                queue.offer(node2.right);
            }
        }
        return t1;
    }
}
退出移动版