树与二叉树

前言：

树这个结构想必在日常生活中很常见到，而现在要介绍的是一种独特的数据结构--二叉树。

1.树

（1）定义：

是一种非线性结构，有一个特殊的节点叫做根节点，树没有前驱节点；树是递归定义的；树形结构中子树不能有交集，否则就不是树形结构。

（2）树相关重要概念：（如上图）

节点的度：一个节点含有的子树的个数。eg：A的度为2，B的度为3。

树的度：一棵树中，所有节点的度中的最大值。 eg：树的度为3.

叶子节点/终端节点：节点的度为0的节点。eg：叶子节点：E，D，G，F

双亲节点/父节点：若有一个节点含有子节点，则称这个节点为该子节点的双亲节点/父节点。

孩子节点/子节点：一个节点含有的子树的根节点称为该节点的子节点。

根节点：一颗树中，没有双亲节点的节点。

节点的层次：从根节点开始，根为第一层，根的子节点为第二层，以此类推。

树的高度/深度：树中节点的最大层次。eg：树的深度/高度为3.

2.二叉树

（1）定义：

该树中每个节点的度都小于等于2；且子树有左右子树之分。下图都是二叉树。

（2）两种特殊的二叉树：

a.完全二叉树：如果一颗树的节点个数为n，深度为K，且树中每一个节点都是深度为K的满二叉树中编号从0~(n-1)的节点，则称为完全二叉树。

b.满二叉树：每层节点数都是最大值 => 如果一颗树的高度为n，且树节点的总数为，则称为满二叉树。

（3）二叉树的性质：

a.若根节点的层数为1，则一颗非空二叉树的第i层上的节点最多有个。

b.若规定只有根节点的二叉树的深度为1，则深度为K的二叉树节点总数最多为。

c.对任何一颗二叉树，如果叶子节点的个数为，节点的度为2的节点个数为，则+1=。

d.具有n个节点的完全二叉树，则该树的深度为向上取整。

e.对于具有n个节点的完全二叉树，如果按照从上到下，从左到右的顺序对所有节点，从0开始编号，对于第i个节点有：

如果i>0，则双亲节点/父节点：；如果i=0，则没有双亲节点/父节点；

如果2i+1<n，则该节点有左孩子；否则没有左孩子。

如果2i+2<n，则该节点有右孩子；否则没有右孩子。

 f.对于一颗完全二叉树来说，如果该树节点总数为偶数个，则节点的度为1的节点只有一个；若为奇数个，则没有节点的度为1的节点。

（4）二叉树的遍历及其代码实现：

在实现二叉树的遍历之前，首先需要创建一个类TreeNode（二叉树的节点，包含该节点的值，该节点的左孩子节点，该节点的右孩子节点），所以：

class TreeNode {public TreeNode left;//左孩子public TreeNode right;//右孩子public int val;public TreeNode(int val) {this.val = val;}
}

a.前序遍历：根节点 -> 左子树 -> 右子树

分析：

代码实现：

public void preorderTraversal(TreeNode root) {if(root == null) {return;}System.out.print(root.val + " ");preorderTraversal(root.left);preorderTraversal(root.right);
}

b.中序遍历：左子树 -> 根节点 -> 右子树

分析：

代码实现：

public void inorderTraversal(TreeNode root) {if(root == null) {return;}preorderTraversal(root.left);System.out.print(root.val + " ");preorderTraversal(root.right);
}

c.后序遍历：左子树 -> 右子树 -> 根节点

分析：

代码实现：

public void lastorderTraversal(TreeNode root) {if(root == null) {return;}preorderTraversal(root.left);preorderTraversal(root.right);System.out.print(root.val + " ");
}

（5）二叉树相关OJ题：

二叉树所有的题都会涉及到递归。所有OJ题的前提都是已经创建好了一颗树，并且知道根节点为root。

a.求树的高度。

题析：

题解：

public int getHeight(TreeNode root) {if(root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.max(leftHeight,rightHeight) + 1;//这里也可以用条件运算符
}

b.求树中叶子节点的个数。

题析：

 题解：

public int getLeafNodeCount(TreeNode root) {if(root == null) {return 0;}if(root.left == null && root.right == null) {return 1;}    return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}

c.第i层有多少个节点。

题析：

题解：

public int getKLevelNodeCount(TreeNode root, int k) {if(root == null) {return 0;}if(k == 1) {return 1;}return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
}

 d.判断某个val值是否存在于树中。

题析：

题解：

public TreeNode getVal(TreeNode root, int val) {if(root == null) {return null;}if(root.val == val) {return root;}TreeNode leftTree = getVal(root.left,val);if(leftTree != null) {return leftTree;}TreeNode rightTree = getVal(root.right,val);if(rightTree != null) {return rightTree;}return null;
}

e.节点的总个数。

题析：

题解：

public int size(TreeNode root) {if(root == null) {return 0;}return size(root.left) + size(root.right) + 1;
}

 f.检查两棵树是否相同

题析：

题解：

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null) {return true;}if(p == null && q != null || q == null && p != null) {return false;}if(p.val != q.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}

 g.另一棵树的子树

题析：

题解：

class Solution {//判断两棵树的结构是否相同private boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null) {return true;}if(p == null && q != null || q == null && p != null) {return false;}if(p.val != q.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null) {return false;}if(isSameTree(root,subRoot)) {return true; }return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}
}

 h.翻转二叉树

题析：

题解：

法一：该种方法没有利用返回值（先序遍历）。

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null) {return null;}if(root.left == null && root.right == null) {return root;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}
}

 法二：利用返回值（后序遍历）。

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null) {return null;}if(root.left == null && root.right == null) {return root;}TreeNode leftNode = invertTree(root.left);TreeNode rightNode = invertTree(root.right);root.left = rightNode;root.right = leftNode;return root;}
}

i.是否为平衡二叉树

题析：

题解：

法一：该方法的时间复杂度为

class Solution {public boolean isBalanced(TreeNode root) {if(root == null) {return true;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);if(Math.abs(leftHeight - rightHeight) > 1) {return false;}  return isBalanced(root.left) && isBalanced(root.right);}private int getHeight(TreeNode root) {if(root == null) {return 0;}int leftHigh = getHeight(root.left);int rightHigh = getHeight(root.right);return Math.max(leftHigh,rightHigh) + 1;}
}

 法二：可以实现时间复杂度为，只需要去修改getHeight方法，在求高度的过程中去判断是否每一个节点的高度差 <= 1。

题解：

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

j.二叉树的构建与遍历

题析：

题解：

import java.util.Scanner;
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}public class Main {private static int i;//注意static修饰的变量，每次调用这个方法的时候都是对同一个变量进行修改的。//所以第二次调用该方法的时候，i不为0.所以需要在while循环中将i置0/使用非静态方法private static TreeNode createTree(String str) {TreeNode root = null;if (str.charAt(i) != '#') {root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);}else {i++;}return root;
}//中序遍历private static void inOrder(TreeNode root) {if(root == null) {return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();i = 0;TreeNode root = createTree(str);inOrder(root);}}
}

 k.对称二叉树

题析：

题解：

class Solution {private boolean isSymmetricChild(TreeNode leftNode, TreeNode rightNode) {if(leftNode == null && rightNode != null || rightNode == null && leftNode != null){return false;}if(leftNode == null && rightNode == null) {return true;}if(leftNode.val != rightNode.val) {return false;}return isSymmetricChild(leftNode.left,rightNode.right) &&             isSymmetricChild(leftNode.right,rightNode.left);}public boolean isSymmetric(TreeNode root) {return isSymmetricChild(root.left, root.right);}
}