判断一个节点是否在一颗子树中

判断一个节点是否在一颗子树中

（使用java语言）递归实现——>
（1）首先根节点入栈；判断node和目标节点值goal是否相等；
（2）node和goal不相等，递归node的左子节点；判断其和goal是否相等；
（3）如果不相等，递归node的右子节点；判断其和goal是否相等；
（4）如果还是不相等则继续执行（2）、（3）步骤，直到找到和goal相等的节点
（5）如果所有节点都遍历完之后还是没找到，则返回false

public class BinaryTree {
	//判断一个节点是否在一颗子树中
	public boolean exist(TreeNode node,int goal) {
	//第一次的时候传入根节点和目标节点
	
		if(node==null) {//根节点为空，树不存在
			return false;
		}
		if(goal==node.getValue()) {
		//目标节点和当前节点的值相同，则表明节点在树中
			return true;
		}
		return exist(node.getLeft(),goal) || exist(node.getRight(),goal);
		//把递归调用写在return后面，可以直接返回递归结果
		//分别递归当前节点的左子节点和右子节点，判断节点值和目标值是否相同
	}
}

测试类：

public class Test {//测试类
	public static void main(String[] args) {
		
		BinaryTree tree=new BinaryTree();
		TreeNode node=new TreeNode(5);
		TreeNode node1=new TreeNode(3);
		TreeNode node2=new TreeNode(7);
		TreeNode node3=new TreeNode(2);
		TreeNode node4=new TreeNode(4);
		TreeNode node5=new TreeNode(6);
		TreeNode node6=new TreeNode(8);
		node.setLeft(node1);
		node.setRight(node2);
		node1.setLeft(node3);
		node1.setRight(node4);
		node2.setLeft(node5);
		node2.setRight(node6);
		//测试：判断一个节点是否在一颗子树中
		System.out.println(tree.exist(node, 4));
		
	}
}

节点类：

public class TreeNode {//节点类
	private TreeNode leftTreeNode;//左子树
	private TreeNode rightTreeNode;//右子树
	private int value;//值
	public TreeNode(int value) {
		this.value=value;
	}
	@Override
    public String toString() {
        return "TreeNode{" +
                "leftTreeNode=" + leftTreeNode +
                ", rightTreeNode=" + rightTreeNode +
                ", value=" + value +
                '}';
    }
	public TreeNode getLeft() {
		return leftTreeNode;
	}
	public void setLeft(TreeNode leftTreeNode) {
		this.leftTreeNode=leftTreeNode;
	}
	public TreeNode getRight() {
		return rightTreeNode;
	}
	public void setRight(TreeNode rightTreeNode) {
		this.rightTreeNode=rightTreeNode;
	}
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value=value;
	}
	

}