二叉树练习

二叉树的遍历方式：

前序遍历：根结点 ---> 左子树 ---> 右子树

		if (root != null) {
			System.out.print(root.val);
			preOrderTraverse1(root.left);
			preOrderTraverse1(root.right);
		}

中序遍历：左子树---> 根结点 ---> 右子树

		if (root != null) {
			preOrderTraverse1(root.left);
            System.out.print(root.val);
			preOrderTraverse1(root.right);
		}

后序遍历：左子树 ---> 右子树 ---> 根结点

	if (root != null) {
			preOrderTraverse1(root.left);
			preOrderTraverse1(root.right);
            System.out.print(root.val);
		}

栈的方式：

首先要注意栈是一端先进后出的容器，比方说我们进行先序遍历，我们并不是按照中，左右的方式入栈，但是我们会按照该方式出栈。

//先序
public void preOrderTraverse2(TreeNode root) {
		LinkedList stack = new LinkedList<>();
		TreeNode pNode = root;
		while (pNode != null || !stack.isEmpty()) {
			if (pNode != null) {
				System.out.print(pNode.val+"  ");
				stack.push(pNode);
				pNode = pNode.left;
			} else { //pNode == null && !stack.isEmpty()
				TreeNode node = stack.pop();
				pNode = node.right;
			}
		}
	}
 
//中序
 
public void inOrderTraverse2(TreeNode root) {
		LinkedList stack = new LinkedList<>();
		TreeNode pNode = root;
		while (pNode != null || !stack.isEmpty()) {
			if (pNode != null) {
				stack.push(pNode);
				pNode = pNode.left;
			} else { //pNode == null && !stack.isEmpty()
				TreeNode node = stack.pop();
				System.out.print(node.val+"  ");
				pNode = node.right;
			}
		}
	}
 
//后序
 
public void levelTraverse(TreeNode root) {
		if (root == null) {
			return;
		}
		LinkedList queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			System.out.print(node.val+"  ");
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
	}

判断二叉树的层情况：

 性质1 ： 二叉树的第 i 层上至多有 2^(i-1) 个结点 (i>=1)

 性质2 ：  深度为 k 的二叉树至多有 2^k -1 个结点( k>=1)

 性质3 ：  对任意的一颗二叉树 T ，若叶子结点数为 n0,而其度数为 2 的结点数为 n2,则 n0 =                            n2+1

 性质4 ：  具有 n 个结点的完全二叉树的深度 [log2n]+1

 性质 5：  如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有

                        (1).如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下                                  取整

                        (2).如果2i>n那么节点i没有左孩子，否则其左孩子为2i

                        (3).如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1
原文链接：https://blog.csdn.net/fsfsfsdfsdfdr/article/details/82454981

 

 

二叉搜索树又称二叉排序树，具有以下性质：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

注意：中序遍历二叉搜索树是有序的。

1.力扣 验证二叉搜索树

 1.1递归

上下界的概念，对于左子树来说，根节点就是上界，而相反，对于右子树来说，根节点是下界。

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
 
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}