二叉树专题

前言
一 . 使用递归和非递归实现二叉树的遍历
- 1.1.递归实现先序遍历，中续遍历，后序遍历
- 1.2.非递归实现先序遍历，中序遍历，后续遍历
二. 二叉树的相关概念及实现判断
三. [给定两个二叉树的节点p和q，找到他们的最近公共祖先节点](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
四. [在二叉算树中找到一个节点的后继节点](https://www.nowcoder.com/practice/c37ec6a9e4084b9c943be2d3a369e177?tpId=101&&tqId=33243&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking)
五. [二叉树的序列化和反序列化](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/)
六. [折纸问题](https://www.nowcoder.com/practice/e0e3459723e04a64900a2ec53bdf8852?tpId=101&&tqId=33128&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking)

前言

点击题目就可以跳转到leetcode或者牛客进练习。

一 . 使用递归和非递归实现二叉树的遍历

1.1.递归实现先序遍历，中续遍历，后序遍历

递归实现相对简单，直接上代码；

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
	class Solution {
	//递归实现先序遍历
    public void pre(TreeNode root,List<Integer> list){
        if(root == null) return;
        list.add(root.val);//根
        pre(root.left,list);//左
        pre(root.right,list);//右
    } 
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        pre(root,list);
        return list;
        }
        
   //递归实现中序遍历
   public void mid(TreeNode root,List<Integer> list){
        if(root == null) return;
        mid(root.left,list);//左
        list.add(root.val);//根
        mid(root.right,list);//右
    } 
    public List<Integer> midorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        mid(root,list);
        return list;
        }

	//递归实现后续遍历
    public void post(TreeNode root,List<Integer> list){
        if(root == null) return;
        post(root.left,list);//左
        post(root.right,list);//右
        list.add(root.val);//根
    } 
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        post(root,list);
        return list;
        }
  	
}

1.2.非递归实现先序遍历，中序遍历，后续遍历

1.2.1 非递归实现先序遍历：

1.前序遍历是跟左右，先把root放入栈中；
2.将栈中元素弹出，并将该元素其按照右孩子，左孩子（如果有的话）的顺序压入栈中；
3.重复操作 2 。

class Solution {
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null)    stack.push(root);//操作1
        while(!stack.isEmpty()){//操作2
            root = stack.pop();
            list.add(root.val);
            if(root.right != null){
                stack.push(root.right);
            }
            if(root.left != null){
                stack.push(root.left);
            }
        }
        return list;
    }
}

1.2.2 非递归实现后序遍历

后续遍历是左右根，前序遍历是根左右，只需把前序遍历的代码修改一下变为根右左放入栈中，再输出就得到了后序遍历。

/** * 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> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> help = new Stack<>();
        if(root != null)    stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            help.push(root);
            if(root.left != null)   stack.push(root.left);
            if(root.right != null)  stack.push(root.right);
        }
        while(!help.isEmpty()){
            list.add(help.pop().val);
        }
        return list;
    }
}

1.2.3 非递归实现中序遍历

1.中序遍历是左跟右，所以我们先一直遍历根节点的左孩子直到为空，并依次压入栈中，并进入操作 2；
2.然后接下来弹出栈顶元素，如果其有右孩子，则将右孩子压入栈中，并重复操作 1。

/** * 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> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            if(root != null){//操作1
                stack.push(root);
                root = root.left;
            }else{//操作2
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }
}

二. 二叉树的相关概念及实现判断

2.1 判断二叉树是否为搜索二叉树

思路相对好想，只要保证root满足以下两条就是BFT：
1.root的所有的左子树都是BFT且所有的右子树都是BFT
2.root的所有左子树中的最大值小于root的值且root的所有右子树的最小值大于root的值；

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    public boolean isBST(TreeNode root,Integer min,Integer max){
        if(root == null)    return true;
        int val = root.val;
        //保证root的左子树的最大值小于root的值，root右子树的最小值大于root的值；
        if(min != null && min >= val)    return false;
        if(max != null && max <= val)    return false;
        //保证root的左子树是BFT，root的右子树是BFT
        if(!isBST(root.left,min,val))   return false;
        if(!isBST(root.right,val,max))  return false;
        
        return true;
    }
    public boolean isValidBST(TreeNode root) {
        if(root == null)    return true;
        return isBST(root,null,null);
    }
}

2.2 判断二叉树是否为完全二叉树

使用宽度优先进行遍历，遍历过程中出现如下情况就不是完全二叉树：
1.遇到左右孩子不为空的节点并且该节点不是叶子节点；
2.遇到节点的左孩子为空且右孩子不为空的时候；

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root == null)    return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean isMeet = false;//表示是否遇到左右孩子不双全的节点
        TreeNode l = null;
        TreeNode r = null;
        while(!queue.isEmpty()){
            root = queue.poll();
            l = root.left;
            r = root.right;
            if(
				//遇到左右孩子不双全并且不是叶子节点的节点的时候，不是完全二叉树
				(isMeet && (l != null || r != null)) 
            	|| 
            	//遇到左孩子为空且右孩子不为空的节点的时候，不是完全二叉树
            	(l == null && r != null)){
              return false;
           }
            if(l != null)    queue.add(l);
            if(r != null)    queue.add(r);
            if(l == null || r == null)     isMeet = true;
        }
        return true;
    }
}

2.3 判断二叉树是否为满二叉树

只要保证节点的个数nodes和二叉树的高度height满足nodes = 2的height次方 - 1就是满二叉树；

public class IsFull {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean isFull1(Node head) {
		if (head == null) {

			return true;
		}
		int height = h(head);
		int nodes = n(head);
		return (1 << height) - 1 == nodes;//位运算速度快
	}
	
	//求深度height
	public static int h(Node head) {
		if (head == null) {
			return 0;
		}
		return Math.max(h(head.left), h(head.right)) + 1;
	}
	//求节点个数nodes
	public static int n(Node head) {
		if (head == null) {
			return 0;
		}
		return n(head.left) + n(head.right) + 1;
	}
}

2.4 求一颗二叉树的最大宽度

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    public int maxWidth(TreeNode root) {
    	int max = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null)    queue.add(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            for(int i = 0;i < n;i++){
                root = queue.poll();
                if(root.left != null)   queue.add(root.left);
                if(root.right != null)  queue.add(root.right);
            }
            max = Math.max(max，n);
        }
        return max;
    }
}

2.5 判断二叉树是否为平衡二叉树

满足左右子树高度不大于1的二叉树为平衡二叉树；

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    public int help(TreeNode root){
        if(root == null)    return -1;
        int left = help(root.left);
        int right = help(root.right);
        return 1 + Math.max(left,right);
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null)    return true;
        if(Math.abs(help(root.left) - help(root.right)) > 1)    return false;
        return isBalanced(root.left) && isBalanced(root.right);  
    }
}

三. 给定两个二叉树的节点p和q，找到他们的最近公共祖先节点

节点的子树中是否含有p和q，以及该节点是不是最低公共子树；

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;//当遍历到底或者遍历到p或q时向上返回root；
        TreeNode left =  lowestCommonAncestor(root.left,p,q);//在左子树中寻找p或q
        TreeNode right = lowestCommonAncestor(root.right,p,q);//在右子树中寻找p或q
        if(left != null && right != null)   return root;//此时证明p和q在分别在该节点的左右子树中；
        return left != null ? left : right;//如果left不为空，证明左子树中含有p或q，否则右子树中含有p或q； 
    }
}

四. 在二叉算树中找到一个节点的后继节点

public class SuccessorNode {

	public static class Node {
		public int value;
		public Node left;
		public Node right;
		public Node parent;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node getSuccessorNode(Node node) {
		if (node == null) {
			return node;
		}
		if (node.right != null) {
			return getLeftMost(node.right);
		} else { // 无右子树
			Node parent = node.parent;
			while (parent != null && parent.right == node) { // 当前节点是其父亲节点右孩子
				node = parent;
				parent = node.parent;
			}
			return parent;
		}
	}

	public static Node getLeftMost(Node node) {
		if (node == null) {
			return node;
		}
		while (node.left != null) {
			node = node.left;
		}
		return node;
}

五. 二叉树的序列化和反序列化

1.按照先序遍历的方式去进行序列化，每遍历一个节点在后面加上""，就会自动转为String，如果遇到节点的左右孩
子有为空的话，就记为"#";
2. 反序列化的时候，先将之前序列化得到的String按照"_",分隔开存入数组中，如果元素为"#"则返回空加下来再将数
组中的元素一次放入队列中，接下来按照先序遍历的顺序（即跟左右）来递归进而得到反序列化的结果。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)    return "#_";
        String res = root.val + "_";//跟
        res += serialize(root.left);//左
        res += serialize(root.right);//右
        return res;

    }

    // Decodes your encoded data to tree.
    public TreeNode desHelp(Queue<String> queue){//按照先序遍历的顺序去进行递归
        String value = queue.poll(); 
        if(value.equals("#"))   return null;
        TreeNode root = new TreeNode(Integer.valueOf(value));//根
        root.left = desHelp(queue);//左
        root.right = desHelp(queue);//右
        return root;
    }
    public TreeNode deserialize(String data) {
        String[] values = data.split("_");//将data按照"_"进行分割并存入数组中
        Queue<String> queue = new LinkedList<>();
        for(int i =0 ; i != values.length ; i++){
            queue.offer(values[i]);//将数组中的元素放入队列中，方便接下来的递鬼
        }
        return desHelp(queue);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

六. 折纸问题

public class Code10_PaperFolding {

	public static void printAllFolds(int N) {
		printProcess(1, N, true);
	}

	public static void printProcess(int i, int N, boolean down) {
		if (i > N) {
			return;
		}
		printProcess(i + 1, N, true);
		System.out.println(down ? "down " : "up ");
		printProcess(i + 1, N, false);
	}

	public static void main(String[] args) {
		int N = 1;
		printAllFolds(N);
	}
}