二叉树

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

       3
     /   \
   4     5
  /  \
1    2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dshwe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路： 简单暴力，从树的根节点往下比较，遍历不匹配，则从左子树遍历，再从右子树遍历。

7. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

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

3
/ \
9 20
/ \
15 7

返回锯齿形层序遍历如下：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路： 一层一层遍历，一层节点遍历完后，添加一个null节点，这个null节点用来辅助判断一层已经遍历完成。

class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List> result = new ArrayList<>();
        LinkedList nodeQueue = new LinkedList<>();
        nodeQueue.addLast(root);
        nodeQueue.addLast(null);

        LinkedList levelList = new LinkedList<>();
        boolean isLeftOrder = true;

        while(nodeQueue.size() > 0){
            TreeNode currNode = nodeQueue.pollFirst();

            if(currNode != null){
                if(isLeftOrder){
                    levelList.addLast(currNode.val);
                }else{
                    levelList.addFirst(currNode.val);
                }
                
                if(currNode.left != null){
                    nodeQueue.addLast(currNode.left);
                }
                if(currNode.right != null){
                    nodeQueue.addLast(currNode.right);
                }
            } else{
                result.add(levelList);
                levelList = new LinkedList<>();
                
                if(nodeQueue.size() > 0){
                    nodeQueue.addLast(null);
                }
                isLeftOrder = !isLeftOrder;
            }
        }

        return result;
    }
}

8. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：

class Solution {
   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        Stack path = new Stack<>();
        Stack node_p_path = new Stack<>();
        Stack node_q_path = new Stack<>();
        boolean found = false;

        preorder(root, path, node_p_path, p, found);
        path = new Stack<>();
        found = false;
        preorder(root,path, node_q_path, q, found);

        int length = 0;
        if(node_p_path.size() < node_q_path.size()){
            length = node_p_path.size();
            while(node_q_path.size() > length){
                node_q_path.pop();
            }
        }
        else{
            length = node_q_path.size();
            while(node_p_path.size() > length){
                node_p_path.pop();
            }
        }

        TreeNode result = null;

        for(int i = 0; i < length; i++){
            if(node_p_path.peek().equals(node_q_path.peek())){
                return new TreeNode(node_p_path.pop());
            }else
            {
                node_p_path.pop();
                node_q_path.pop();
            }
        }

        return result;
    }

    private void preorder(TreeNode root, Stack path, Stack node_p_path, TreeNode p, boolean found) {

        if(root == null || found){
            return;
        }
        path.push(root.val);

        if(root == p){
            found = true;
            node_p_path.addAll(path);
        }

        preorder(root.left, path, node_p_path, p, found);
        preorder(root.right,path, node_p_path, p, found);

        path.pop();
    }
}

方法2：

class Solution {
Map parent = new HashMap();
Set visited = new HashSet();

public void dfs(TreeNode root) {
      if (root.left != null) {
             parent.put(root.left.val, root);
             dfs(root.left);
      }
     if (root.right != null) {
           parent.put(root.right.val, root);
          dfs(root.right);
     }
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      dfs(root);
      while (p != null) {
           visited.add(p.val);
           p = parent.get(p.val);
      }
     while (q != null) {
         if (visited.contains(q.val)) {
         return q;
         }
         q = parent.get(q.val);
      }
     return null;
   }
}

方法三：

public class FindLowestAncestor {
　　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 && right != null) {
　　　　　　return root;
　　　　}
　　　　if(left == null && right == null) {
　　　　　　return null;
　　　　}

　　　　return left == null ? right : left;
　　}
}

687. 最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

              5
             / \
            4   5
           / \   \
          1   1   5

输出:

2

示例 2:

输入:

              1
             / \
            4   5
           / \   \
          4   4   5

输出:

2

class Solution {
    int maxLines = 0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return maxLines;
    }

    private int dfs(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) {
            return 0;
        }
        
        int leftCount = dfs(root.left);
        int rightCount = dfs(root.right);

        if(root.left != null) {
            if(root.left.val == root.val) {
                leftCount++;
            } else {
                leftCount = 0;
            }
        }
        if(root.right != null) {
            if(root.right.val == root.val) {
                rightCount++;
            } else {
                rightCount = 0;
            }
        }
        maxLines = Math.max(maxLines, leftCount + rightCount);
        return Math.max(leftCount, rightCount);
    }
}