二叉树专题

时间:2020-8-2 作者:admin


二叉树专题

前言

点击题目就可以跳转到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);
	}
}
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。